Today I was solving pG in this problem list. When I submit my code it seems alright at the first few test case but turns out to be an judgement fail. Does someone know the reason behind it?
Here is my 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; //using Vector = complex; //using Segment = pair<Point, Point>;
/* enum { NO_SOL, MULTI_SOL, ONE_SOL }; */ vector 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 > vec(N, vector(3)); for(int i = 0; i < N; i++) { cin >> vec[i][0] >> vec[i][1] >> vec[i][2]; } sort(vec.begin(), vec.end(), [](vector a, vector 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 > vec(N, vector(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 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 &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; }