#pragma GCC optimize("02,unroll-loops") #include <bits/stdc++.h> #define FOR(i, l, r) for(int i = l; i <= r; i++) #define FOD(i, r, l) for(int i = r; i >= l; i--) #define rep(i, n) for(int i = 0; i < n; i++) #define pb push_back #define ep emplace_back #define fi first #define se second #define sz(A) (int) A.size() #define bit(mask, i) ((mask >> i) & 1) #define lon(x) ((1ll << x)) #define all(A) A.begin(), A.end() #define el cout << '\n'; #define IOI_26_Gold_Medalist int main() using namespace std; const int maxn = 1e6 + 5; const int mod = 1e9 + 7; using ii = pair<int, int>; using ll = long long; const ll inf = 3e18; using str = string; using vi = vector<int>; template <class X, class Y> bool minimize(X &x, const Y &y) { if(x > y) { x = y; return true; } else return false; } template <class X, class Y> bool maximize(X &x, const Y &y) { if(x < y) { x = y; return true; } else return false; } int n; vector<ii> pts; namespace sub1 { int ans = 0; void solve() { unordered_map<int, int> cntx, cnty; rep(mask, lon(n)) { bool valid = true; cntx.clear(); cnty.clear(); rep(i, n) if(bit(mask, i)) { cntx[pts[i].fi]++; cnty[pts[i].se]++; if(cntx[pts[i].fi] > 2) valid = false; if(cnty[pts[i].se] > 2) valid = false; if(!valid) break; } if(!valid) continue; rep(i, n) if(!bit(mask, i)) { bool okL = false, okR = false; rep(j, n) if(bit(mask, j)) { if(pts[j].fi == pts[i].fi) { if(pts[j].se < pts[i].se) okL = true; else okR = true; } } if(okL && okR) continue; bool okT = false, okB = false; rep(j, n) if(bit(mask, j)) { if(pts[j].se == pts[i].se) { if(pts[j].fi < pts[i].fi) okT = true; else okB = true; } } if(okT && okB) continue; valid = false; break; } if(valid) ans = mask; } rep(i, n) cout << bit(ans, i); } } namespace sub2 { unordered_map<int, int> cntx; bool check() { rep(i, n) { cntx[pts[i].fi]++; if(cntx[pts[i].fi] > 2) return false; } return true; } void solve() { vi comp; for(auto &pr : pts) { int x = pr.se; comp.pb(x); } sort(all(comp)); comp.erase(unique(all(comp)), comp.end()); int K = sz(comp); vi maxR(K + 1, 0), minR(K + 1, 1e9), idmaxR(K + 1, 0), idminR(K + 1, 0); rep(i, n) { int x = lower_bound(all(comp), pts[i].se) - comp.begin() + 1; if(maximize(maxR[x], pts[i].fi)) { idmaxR[x] = i; } if(minimize(minR[x], pts[i].fi)) { idminR[x] = i; } } vi dd(n, 0); FOR(i, 1, K) { dd[idmaxR[i]] = 1; dd[idminR[i]] = 1; // cerr << maxR[i] << " " << minR[i] << endl; } rep(i, n) cout << dd[i]; } } namespace sub3 { int ans[maxn]; vector<pair<int,int>> col[maxn], row[maxn]; int cnt[maxn]; void solve() { int maxX = 0, maxY = 0; rep(i, n) { maximize(maxX, pts[i].fi); maximize(maxY, pts[i].se); } for (int x = 0; x <= maxX; ++x) { col[x].clear(); cnt[x] = 0; } for (int y = 0; y <= maxY; ++y) row[y].clear(); rep(i, n) ans[i] = 0; rep(i, n) { int x = pts[i].fi, y = pts[i].se; col[x].ep(y, i); row[y].ep(x, i); } for (int x = 0; x <= maxX; ++x) { if (col[x].empty()) continue; sort(all(col[x])); int idBot = col[x].front().second; int idTop = col[x].back().second; if (!ans[idBot]) { ans[idBot] = 1; cnt[x]++; } if (idTop != idBot && !ans[idTop]) { if (cnt[x] < 2) { ans[idTop] = 1; cnt[x]++; } } } for (int y = 0; y <= maxY; ++y) { if (row[y].empty()) continue; sort(all(row[y])); int xL = row[y].front().first, idL = row[y].front().second; int xR = row[y].back().first, idR = row[y].back().second; if (!ans[idL] && cnt[xL] < 2) { ans[idL] = 1; cnt[xL]++; } if (!ans[idR] && cnt[xR] < 2) { ans[idR] = 1; cnt[xR]++; } } rep(i, n) cout << ans[i]; } } IOI_26_Gold_Medalist { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define TASK "SLAMP" if(fopen(TASK".INP", "r")) { freopen(TASK".INP", "r", stdin); freopen(TASK".OUT", "w", stdout); } cin >> n; rep(i, n) { int x, y; cin >> x >> y; pts.ep(x, y); } if(n <= 16) return sub1 :: solve(), 0; if(sub2 :: check()) return sub2 :: solve(), 0; return sub3 :: solve(), 0; return 0; } /* 3 1 1 1 5 1 4 9 1 1 1 2 5 3 2 1 4 2 2 3 3 1 3 2 4 3 111011100 111001011 8 1 2 1 4 1 5 2 2 2 5 4 2 4 4 4 5 10100101 10111101 */

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