#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define eb emplace_back #define vi vector<int> #define pi pair<int,int> #define sz(v) (int)(v).size() #define all(v) (v).begin(), (v).end() #define compact(v) (v).erase(unique(all(v)), (v).end()) template<class T> using upq = priority_queue<T, vector<T>, greater<T>>; template<class T> int lwrbound(const vector<T>& a, const T& b, const int s = 0){return int(lower_bound(s + all(a), b) - a.begin());} template<class T> int uprbound(const vector<T>& a, const T& b, const int s = 0){return int(upper_bound(s + all(a), b) - a.begin());} #define FOR(i, a, b) for(int i = (a); i <= (b); i++) #define ROF(i, a, b) for(int i = (a); i >= (b); i--) #define sumof(x) accumulate(all(x), 0ll) #define dbg(x) "[" << #x " = " << (x) << "]" #define el "\n" using ll = long long; using ld = long double; template<class T> bool ckmx(T& a, const T b){return (a < b ? a = b, true : false);} template<class T> bool ckmn(T& a, const T b){return (a > b ? a = b, true : false);} const int MAX = 1e6 + 5; /* column j is holding which ? what is the next in column j of start, ed ? what is the previous in row i ? i am so stupid TvT, preprocess is way more easier + only 2 in each row why we need to use compress ??? me stupid TvT */ int N, X[MAX], Y[MAX]; int st[MAX], ed[MAX], stC[MAX], edC[MAX]; int nxt[MAX], prv[MAX], ans[MAX]; vi col[MAX]; void add(int i, int d){ int x = X[i], y = Y[i]; (d > 0 ? stC[y] = i : edC[y] = i); if(stC[y] && edC[y] && X[stC[y]] > X[edC[y]]){ stC[y] = edC[y] = 0; return; } if(!st[x]){ st[x] = i; } else if(!ed[x]){ ed[x] = i; if(Y[ed[x]] < Y[st[x]]){ swap(st[x], ed[x]); } } else{ if(i == st[x] || i == ed[x]) return; if(y < Y[st[x]]) swap(i, st[x]); if(y > Y[ed[x]]) swap(i, ed[x]); d = (X[stC[Y[i]]] < X[i] ? -1 : +1); int j = (d > 0 ? nxt[i] : prv[i]); if(j > 0) add(j, d); } } void Main() { cin >> N; FOR(i, 1, N){ cin >> X[i] >> Y[i]; col[Y[i]].eb(i); } FOR(_, 1, MAX - 1) if(sz(col[_])){ sort(all(col[_]), [&](int x, int y){ return X[x] < X[y]; }); int lst = 0; for(int i : col[_]){ if(lst > 0){ nxt[lst] = i; prv[i] = lst; } lst = i; } add(col[_][0], +1); add(col[_].back(), -1); } FOR(_, 1, MAX - 1) if(st[_]){ ans[st[_]] = ans[ed[_]] = 1; } auto brute = [&]() -> void{ FOR(i, 1, N) if(!ans[i]){ int good = 0; FOR(j, 1, N) if(ans[j]){ FOR(k, 1, N) if(ans[k]){ if(X[j] == X[k] && X[k] == X[i]){ if(min(Y[j], Y[k]) < Y[i] && Y[i] < max(Y[j], Y[k])){ good = 1; } } if(Y[j] == Y[k] && Y[k] == Y[i]){ if(min(X[j], X[k]) < X[i] && X[i] < max(X[j], X[k])){ good = 1; } } } } if(!good){ cout << "NGU " << i << el; return; } } map<int, int> cntX, cntY; FOR(i, 1, N) if(ans[i]){ ++cntX[X[i]], ++cntY[Y[i]]; } for(auto it : cntX) if(it.se > 2) cout << "NGUX: " << it.fi << el; for(auto it : cntY) if(it.se > 2) cout << "NGUY: " << it.fi << el; }; brute(); FOR(i, 1, N) cout << ans[i]; cout << el; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define name "InvMOD" if(fopen(name".INP", "r")){ freopen(name".INP", "r", stdin); freopen(name".OUT", "w", stdout); } int t = 1; while(t--) Main(); return 0; }

Main.cpp: In function 'int32_t main()':
Main.cpp:154:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~