Today I was solving pG in this problem list. When I submit my code it seems alright at the first few test cases but turns out to be an judgement fail. Does someone know the reason behind it?
Here is my code:
code
#include<bits/stdc++.h>
//#define x() real()
//#define y() imag()
//#define int long long
//#define double long double
using namespace std;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
//using Point = complex<double>;
//using Vector = complex<double>;
//using Segment = pair<Point, Point>;
/*
enum {
NO_SOL,
MULTI_SOL,
ONE_SOL
};
*/
vector<pii> ans;
map<int, int> Plus, Minus;
int check(pii xBound, pii yBound) {
if (Plus.size() > 1 or Minus.size() > 1) {
return 0;
}
int pfir, mfir;
if (Plus.size() == 1) {
for(pii X : Plus)
pfir = X.first;
}
if (Minus.size() == 1) {
for(pii X : Minus)
mfir = X.first;
}
if (Plus.size() == 1 and Minus.size() == 1) {
int x = (pfir + mfir) / 2;
int y = (pfir — mfir) / 2;
if (x + y != pfir or x — y != mfir)
return 0;
if (xBound.first <= x and x < xBound.second and
yBound.first <= y and y < yBound.second) {
ans.emplace_back(make_pair(x, y));
return 2;
} else
return 0;
} else if (Plus.size() == 1) {
int D1 = xBound.first + yBound.first;
int D2 = (xBound.second — 1) + (yBound.second — 1);
if (pfir == D1) {
ans.emplace_back(make_pair(xBound.first, yBound.first));
return 2;
} else if (pfir == D2) {
ans.emplace_back(make_pair(xBound.second - 1, yBound.second - 1));
return 2;
} else if (D1 < pfir and pfir < D2)
return 1;
else
return 0;
} else if (Minus.size() == 1) {
int D1 = xBound.first — (yBound.second — 1);
int D2 = (xBound.second — 1) — yBound.first;
if (mfir == D1) {
ans.emplace_back(make_pair(xBound.first, yBound.second - 1));
return 2;
} else if (mfir == D2) {
ans.emplace_back(make_pair(xBound.second - 1, yBound.first));
return 2;
} else if (D1 < mfir and mfir < D2)
return 1;
else
return 0;
}
return 3;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(NULL);
int N; cin >> N;
/*
vector<vector<int> > vec(N, vector<int>(3));
for(int i = 0; i < N; i++) {
cin >> vec[i][0] >> vec[i][1] >> vec[i][2];
}
sort(vec.begin(), vec.end(), [](vector<int> a, vector<int> b) {
if (a[1] == b[1])
return a[0] == b[0] ? a[2] < b[2] : a[0] < b[0];
else
return a[1] < b[1];
});
*/
vector<pair<pii, int> > whyJudgeFail(N);
for(int i = 0; i < N; i++)
cin >> whyJudgeFail[i].first.second >> whyJudgeFail[i].first.first >>
whyJudgeFail[i].second;
sort(whyJudgeFail.begin(), whyJudgeFail.end());
vector<vector<int> > vec(N, vector<int>(3, 0));
for(int i = 0; i < N; i++) {
vec[i][0] = whyJudgeFail[i].first.second;
vec[i][1] = whyJudgeFail[i].first.first;
vec[i][2] = whyJudgeFail[i].second;
}
vector<int> Xcor, Ycor;
for(int i = 0; i < N; i++) {
Xcor.emplace_back(vec[i][0]);
Ycor.emplace_back(vec[i][1]);
}
Xcor.emplace_back(-1e7);
Ycor.emplace_back(-1e7);
Xcor.emplace_back(1e7);
Ycor.emplace_back(1e7);
sort(Xcor.begin(), Xcor.end());
sort(Ycor.begin(), Ycor.end());
N += 2;
bool infSol = false;
for(int i = 0; i < N — 1; i++) {
Plus.clear();
Minus.clear();
pii xRange = make_pair(Xcor[i], Xcor[i + 1]); //[L, R)
if (xRange.first == xRange.second)
continue;
for(vector<int> &VEC : vec) {
if (VEC[0] <= xRange.first) {
if (Minus.find(Minus[VEC[0] — VEC[1] + VEC[2]]) == Minus.end())
Minus[VEC[0] — VEC[1] + VEC[2]] = 1;
else
Minus[VEC[0] — VEC[1] + VEC[2]] += 1;
} else {
if (Plus.find(VEC[0] + VEC[1] — VEC[2]) == Plus.end())
Plus[VEC[0] + VEC[1] — VEC[2]] = 1;
else
Plus[VEC[0] + VEC[1] — VEC[2]] += 1;
}
}
int tmp = check(xRange, make_pair(Ycor[0], Ycor[1]));
if (tmp == 1)
infSol = true;
int idx = 0;
for(int j = 1; j < N - 1; j++) {
pii yRange = make_pair(Ycor[j], Ycor[j + 1]);
if (yRange.first == yRange.second)
continue;
while(idx < vec.size() and vec[idx][1] <= Ycor[j]) {
if (vec[idx][0] <= xRange.first) {
int origin = vec[idx][0] - vec[idx][1] + vec[idx][2];
if (--Minus[origin] == 0)
Minus.erase(origin);
if (Plus.find(vec[idx][0] + vec[idx][1] + vec[idx][2]) == Plus.end())
Plus[vec[idx][0] + vec[idx][1] + vec[idx][2]] = 1;
else
Plus[vec[idx][0] + vec[idx][1] + vec[idx][2]] += 1;
} else {
int origin = vec[idx][0] + vec[idx][1] - vec[idx][2];
if (--Plus[origin] == 0)
Plus.erase(origin);
if (Minus.find(vec[idx][0] - vec[idx][1] - vec[idx][2]) == Minus.end())
Minus[vec[idx][0] - vec[idx][1] - vec[idx][2]] = 1;
else
Minus[vec[idx][0] - vec[idx][1] - vec[idx][2]] += 1;
}
idx++;
}
int tmp = check(xRange, yRange);
if (tmp == 1)
infSol = true;
}
}
sort(ans.begin(), ans.end());
ans.resize(unique(ans.begin(), ans.end()) — ans.begin());
if (infSol or ans.size() > 1)
cout << "uncertain\n";
else if (ans.size() == 1)
cout << ans[0].first << ' ' << ans[0].second << '\n';
else
cout << "impossible\n";
return 0;
}
UPD: The problem has already be fixed, and the code has been rejudged :D
Auto comment: topic has been updated by Misuki (previous revision, new revision, compare).
Because YOU are SUCH a fayyyylure. Look at other people of your age, they're all becoming red and you're stuck at blue. It's because of that phone you're glued to has made you a fayyyylure. Learn from tourist, he practices so hard that he's number 1, if you practice 40 hours a day, you will become like him too. When I was your age, I practiced minimum 50 hours,that too without internet, I also never read an editorial so that I ensured I solved it all by myself. Now stop writing this blog, and no leisure internet browsing from now on!!! Otherwise your peers will out perform you, it is very shameful for me. Go NOW! ~
If you practiced 50 hours then why are you are unrated?
On a more serious note please don't troll as this is a serious issue and can cause problems during contests.
lol it took you 50 hours to solve 1579A - Casimir's String Solitaire
Auto comment: topic has been updated by Misuki (previous revision, new revision, compare).