Today I was solving [pG in this problem list](https://mirror.codeforces.com/gym/101490).↵
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?↵
↵
[picture](/predownloaded/7c/61/7c612ea74d484e0d19add83804759cbdcaab804c.png)↵
↵
Here is my code:↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
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?↵
↵
[picture](/predownloaded/7c/61/7c612ea74d484e0d19add83804759cbdcaab804c.png)↵
↵
Here is my code:↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
