#include <bits/stdc++.h> #define FOR(i,a,b) for (long long i = (a), _b = (b); i <= _b; i++) #define FORD(i,b,a) for (long long i = (b), _a = (a); i>= _a; i--) #define REP(i,n) for( long long i = 0, _n = (n); i < _n; i++) #define all(v) (v).begin(),(v).end() #define fi first #define se second #define MASK(i) (1<<(i)) #define BIT(x,i) ((x) >> (i) & 1) #define div ___div #define prev ___prev #define left ___left #define right ___right #define __builtin_popcount __builtin_popcountll #define file(task) if(fopen(task".inp","r")) freopen(task".inp","r",stdin), freopen(task".out","w",stdout); using namespace std; 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; } const int N = 1e6+5; int mxCol[N], mnCol[N], mxRow[N], mnRow[N], cntRow[N], cntCol[N], LightCol[N], LightRow[N]; vector<int> pos1[N], pos2[N]; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); if(fopen("input.txt","r")){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); } // freopen("SLAMP.inp","r",stdin); // freopen("SLAMP.out","w",stdout); int n; cin >> n; FOR(i,1,N-1) mnCol[i] = N, mnRow[i] = N; pair<int,int> a[n+1]; FOR(i,1,n) { cin >> a[i].first >> a[i].second; maximize(mxRow[a[i].first], a[i].second); minimize(mnRow[a[i].first], a[i].second); maximize(mxCol[a[i].second], a[i].first); minimize(mnCol[a[i].second], a[i].first); } if(n <= 16){ REP(mask, MASK(n)){ vector<int>Light(n+1,0); FOR(i,1,n) { int x = a[i].first, y = a[i].second; mxRow[x] = 0; mnRow[x] = N; mxCol[y] = 0; mnCol[y] = N; cntRow[x] = 0; cntCol[y] = 0; } FOR(i,1,n) { if(BIT(mask,i-1)){ maximize(mxRow[a[i].first], a[i].second); minimize(mnRow[a[i].first], a[i].second); maximize(mxCol[a[i].second], a[i].first); minimize(mnCol[a[i].second], a[i].first); Light[i] = 1; cntRow[a[i].first]++; cntCol[a[i].second]++; } } bool ok = true; FOR(i,1,n) if(cntRow[a[i].first] > 2 || cntCol[a[i].second] > 2) ok = false; FOR(i,1,n){ if(Light[i]) continue; int x = a[i].first, y = a[i].second; if(cntRow[x] < 2 && cntCol[y] < 2) ok = false; // cerr << i << ' ' << x << ' ' << y << ' ' << mnRow[x] << ' ' << mxRow[x] << ' ' << mnCol[y] << ' ' << mxCol[y] << '\n'; if(!(mnRow[x] <= y && y <= mxRow[x]) && !(mnCol[y] <= x && x <= mxCol[y])) ok = false; } if(ok){ FOR(i,1,n) cout << BIT(mask,i-1); cout << '\n'; break; } } // return 0; } FOR(i,1,n) { int x = a[i].first, y = a[i].second; mxRow[x] = 0; mnRow[x] = N; mxCol[y] = 0; mxCol[y] = N; cntRow[x] = 0; cntCol[y] = 0; } vector<bool>Light(n+1,0); while(true){ bool ok = true; FOR(i,1,n) { if(Light[i]) continue; int x = a[i].first, y = a[i].second; if(cntRow[x] < 2 && cntCol[y] < 2) ok = false; } if(ok) break; FOR(i,1,N-1) mnCol[i] = N, mnRow[i] = N, mxCol[i] = 0, mxRow[i] = 0; FOR(i,1,n){ if(Light[i]) continue; int x = a[i].first; int y = a[i].second; if(cntRow[x] < 2 && cntCol[y] < 2){ if(LightRow[x] == 0){ maximize(mxRow[a[i].first], a[i].second); minimize(mnRow[a[i].first], a[i].second); } else if(LightRow[x] == 2){ minimize(mnRow[a[i].first], a[i].second); } else if(LightRow[x] == 1){ maximize(mxRow[a[i].first], a[i].second); } if(LightCol[y] == 0){ maximize(mxCol[a[i].second], a[i].first); minimize(mnCol[a[i].second], a[i].first); } else if(LightCol[y] == 2){ minimize(mnCol[a[i].second], a[i].first); } else if(LightCol[y] == 1){ maximize(mxCol[a[i].second], a[i].first); } } } bool change = false; FOR(i,1,n){ if(Light[i]) continue; int x = a[i].first; int y = a[i].second; if(max(cntRow[x], cntCol[y]) >= 2) continue; if((mxRow[x] == y || mnRow[x] == y) && (mxCol[y] == x || mnCol[y] == x)) { change = true; Light[i] = 1; if(mxRow[x] == y) LightRow[x] = 2; else LightRow[x] = 1; // 1 right 2 left 0 nah if(mxCol[y] == x) LightCol[y] = 2; else LightCol[y] = 1; // 1 up 2 down 0 nah cntRow[x]++; cntCol[y]++; } } if(change == false){ FOR(i,1,n){ if(Light[i]) continue; int x = a[i].first; int y = a[i].second; if(max(cntRow[x], cntCol[y]) >= 2) continue; change = true; Light[i] = 1; if(mxRow[x] == y) LightRow[x] = 2; else LightRow[x] = 1; // 1 right 2 left 0 nah if(mxCol[y] == x) LightCol[y] = 2; else LightCol[y] = 1; // 1 up 2 down 0 nah cntRow[x]++; cntCol[y]++; break; } } } FOR(i,1,n) cout << Light[i]; cerr << "\nTime elapsed: " << clock() * 1.000 / CLOCKS_PER_SEC << " ms.\n"; return 0; }

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