#include <bits/stdc++.h> using namespace std; #define int long long #define pp pair <int, int> #define fi first #define se second #define yes cout << "YES\n" #define no cout << "NO\n" const int N = 1e6 + 9; const int mod = 1e9 + 7; const int INF = 1e18 + 9; void add (int &a, int b){ a += b; if (a >= mod) a -= mod; } void sub (int &a, int b){ a -= b; if (a < 0) a += mod; } int n; struct point { int x; int y; int idx; } pts[N]; int res[N]; vector <int> grpX[N], grpY[N]; int cntRow[N], cntCol[N]; namespace sub1 { bool check (int mask){ int mx = 0; for (int i = 1; i <= n; i++) if (mask >> (i - 1) & 1){ cntRow[pts[i].x]++; cntCol[pts[i].y]++; mx = max ({mx, cntRow[pts[i].x], cntCol[pts[i].y]}); } for (int i = 1; i <= n; i++){ cntRow[pts[i].x] = 0; cntCol[pts[i].y] = 0; } if (mx > 2){ for (int i = 1; i <= n; i++){ cntRow[pts[i].x] = 0; cntCol[pts[i].y] = 0; } return 0; } for (int i = 1; i <= n; i++){ if (mask >> (i - 1) & 1) continue; int onL = 0, onR = 0; for (int idx : grpX[pts[i].x]){ if ((mask >> (idx - 1) & 1) ^ 1) continue; if (pts[idx].y < pts[i].y) onL = 1; if (pts[idx].y > pts[i].y) onR = 1; } if (onL && onR) continue; onL = 0; onR = 0; for (int idx : grpY[pts[i].y]){ if ((mask >> (idx - 1) & 1) ^ 1) continue; if (pts[idx].x < pts[i].x) onL = 1; if (pts[idx].x > pts[i].x) onR = 1; } if (onL && onR) continue; return 0; } return 1; } void solve (){ for (int mask = 0; mask < (1 << n); mask++){ if (check (mask)){ for (int i = 0; i < n; i++) cout << (mask >> i & 1); exit (0); } } exit (0); } } namespace sub2 { bool valid (){ for (int i = 1; i <= n; i++) if (grpX[pts[i].x].size () > 2) return 0; return 1; } void solve (){ vector <int> res (n, 0); for (int i = 1; i <= 1000000; i++){ if (grpY[i].empty ()) continue; res[grpY[i][0] - 1] = 1; res[grpY[i].back () - 1] = 1; } for (int i : res) cout << i; exit (0); } } int Ly[N], Ry[N]; bool needFill (int x){ for (int i : grpX[x]){ int y = pts[i].y; if (Ly[y] == -1 || Ry[y] == -1) return 1; if (Ly[y] < x && x < Ry[y]){ } else return 1; } return 0; } void upd (int y, int x){ if (Ly[y] == -1 || Ly[y] > x) Ly[y] = x; if (Ry[y] == -1 || Ry[y] < x) Ry[y] = x; } void solve (){ cin >> n; for (int i = 1; i <= n; i++){ cin >> pts[i].x >> pts[i].y; pts[i].idx = i; } for (int i = 1; i <= n; i++){ grpX[pts[i].x].push_back (pts[i].idx); grpY[pts[i].y].push_back (pts[i].idx); } if (sub2::valid ()) sub2::solve (); if (n <= 16) sub1::solve (); for (int i = 1; i <= 1000000; i++) Ly[i] = Ry[i] = -1; for (int i = 1; i <= 1000000; i++) sort (grpX[i].begin (), grpX[i].end (), [&](int z1, int z2){ return pts[z1].y < pts[z2].y; }); vector <int> res (n, 0); int L = 1, R = 1000000; while (1){ while (L <= R && needFill (L) == 0) L++; if (L > R) break; while (L <= R && needFill (R) == 0) R--; if (L > R) break; // int stL = 0, enL = 0; for (int i : grpX[L]){ int y = pts[i].y; if (Ly[y] == -1 || Ry[y] == -1){ stL = i; break; } if (Ly[y] < L && L < Ry[y]){ } else { stL = i; break; } } for (int i = grpX[L].size () - 1; i >= 0; i--){ int y = pts[grpX[L][i]].y; if (Ly[y] == -1 || Ry[y] == -1){ enL = grpX[L][i]; break; } if (Ly[y] < L && L < Ry[y]){ } else { enL = grpX[L][i]; break; } } res[pts[stL].idx - 1] = res[pts[enL].idx - 1] = 1; upd (pts[stL].y, pts[stL].x); upd (pts[enL].y, pts[enL].x); // phase 2 int stR = 0, enR = 0; for (int i : grpX[R]){ int y = pts[i].y; if (Ly[y] == -1 || Ry[y] == -1){ stR = i; break; } if (Ly[y] < R && R < Ry[y]){ } else { stR = i; break; } } for (int i = grpX[R].size () - 1; i >= 0; i--){ int y = pts[grpX[R][i]].y; if (Ly[y] == -1 || Ry[y] == -1){ enR = grpX[R][i]; break; } if (Ly[y] < R && R < Ry[y]){ } else { enR = grpX[R][i]; break; } } res[pts[stR].idx - 1] = res[pts[enR].idx - 1] = 1; upd (pts[stR].y, pts[stR].x); upd (pts[enR].y, pts[enR].x); L++; R--; } for (int i : res) cout << i; } bool END; void reset (){ } signed main (){ ios_base::sync_with_stdio (false); cin.tie (NULL); cout.tie (NULL); if (fopen ("slamp.inp", "r")){ freopen ("slamp.inp", "r", stdin); freopen ("slamp.out", "w", stdout); } int t = 1; // cin >> t; while (t--){ solve (); reset (); } } // <33

Main.cpp: In function 'int main()':
Main.cpp:208:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  208 |         freopen ("slamp.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:209:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  209 |         freopen ("slamp.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~