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