/* AUTHOR: TUAN ANH - BUI */ // ~~ icebear ~~ #include <bits/stdc++.h> using namespace std; #define int long long typedef long long ll; typedef pair<int, int> ii; typedef pair<int, ii> iii; template<class X, class Y> bool minimize(X &x, const Y &y) { if (x > y) return x = y, true; return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { if (x < y) return x = y, true; return false; } #define FOR(i,a,b) for(int i=(a); i<=(b); ++i) #define FORR(i,a,b) for(int i=(a); i>=(b); --i) #define REP(i, n) for(int i=0; i<(n); ++i) #define RED(i, n) for(int i=(n)-1; i>=0; --i) #define MASK(i) (1LL << (i)) #define BIT(S, i) (((S) >> (i)) & 1) #define mp make_pair #define pb push_back #define fi first #define se second #define all(x) x.begin(), x.end() #define task "slamp" /*END OF TEMPLATE. ICEBEAR AND THE CAT WILL WIN VOI26 */ const int MOD = 1e9 + 7; const int inf = (int)1e9 + 27092008; const ll INF = (ll)1e18 + 27092008; const int N = 1e6 + 5; int n; vector<ii> saveY[N]; int Ly[N], Ry[N]; // y for same x int Lx[N], Rx[N]; // x for same y int cntX[N], cntY[N]; struct Lamp { int x, y, id; bool operator < (const Lamp &other) const { return x < other.x; } } p[N]; namespace Subtask12 { bool check() { return n <= 16; } void solve() { REP(mask, MASK(n)) { REP(i, n) { Lx[p[i].y] = Ly[p[i].x] = inf; Rx[p[i].y] = Ry[p[i].x] = -inf; cntX[p[i].x] = cntY[p[i].y] = 0; } bool ok = true; REP(i, n) if (BIT(mask, i)) { minimize(Lx[p[i].y], p[i].x); maximize(Rx[p[i].y], p[i].x); minimize(Ly[p[i].x], p[i].y); maximize(Ry[p[i].x], p[i].y); cntX[p[i].x]++; cntY[p[i].y]++; if (cntX[p[i].x] > 2 || cntY[p[i].y] > 2) ok = false; } REP(i, n) if (!BIT(mask, i)) { int x = p[i].x, y = p[i].y; if ((Lx[y] < x && x < Rx[y]) || (Ly[x] < y && y < Ry[x])) continue; ok = false; } if (ok) { REP(i, n) cout << BIT(mask, i); exit(0); } } } } namespace Subtask6 { string ans; void solve() { REP(i, n) ans.pb('0'); FOR(i, 1, N - 5) sort(all(saveY[i])); vector<int> saveX; REP(i, n) saveX.pb(p[i].x); sort(all(saveX)); saveX.resize(unique(all(saveX)) - saveX.begin()); memset(Lx, 0x3f, sizeof Lx); memset(Ly, 0x3f, sizeof Ly); memset(Rx, -0x3f, sizeof Rx); memset(Ry, -0x3f, sizeof Ry); for(int x : {saveX[0], saveX.back()}) { int y, id; tie(y, id) = saveY[x][0]; minimize(Lx[y], x); maximize(Rx[y], x); minimize(Ly[x], y); maximize(Ry[x], y); ans[id] = '1'; tie(y, id) = saveY[x].back(); minimize(Lx[y], x); maximize(Rx[y], x); minimize(Ly[x], y); maximize(Ry[x], y); ans[id] = '1'; } vector<Lamp> stuck; FOR(i, 1, (int)saveX.size() - 2) { int j = 0, x = saveX[i]; bool inStuck = false; while(j < (int)saveY[x].size()) { int y, id; tie(y, id) = saveY[x][j]; if (Lx[y] < x && x < Rx[y]) { j++; continue; } else if (x < Lx[y]) { ans[id] = '1'; minimize(Lx[y], x); maximize(Rx[y], x); minimize(Ly[x], y); maximize(Ry[x], y); cntX[x]++; } break; } int k = saveY[x].size() - 1; while(k >= 0) { int y, id; tie(y, id) = saveY[x][k]; if (Lx[y] < x && x < Rx[y]) { k--; continue; } else if (x < Lx[y] && !inStuck) { ans[id] = '1'; minimize(Lx[y], x); maximize(Rx[y], x); minimize(Ly[x], y); maximize(Ry[x], y); cntX[x]++; k--; continue; } inStuck = true; stuck.pb({x, y, id}); k--; } } FOR(i, 1, N - 5) saveY[i].clear(); saveX.clear(); for(auto lamp : stuck) { // cout << lamp.x << ' ' << lamp.y << ' ' << lamp.id << '\n'; saveX.pb(lamp.x); saveY[lamp.x].pb(mp(lamp.y, lamp.id)); } sort(all(saveX), greater<int>()); saveX.resize(unique(all(saveX)) - saveX.begin()); for(int &x : saveX) { if (cntX[x] == 2) continue; sort(all(saveY[x])); for(auto &y : saveY[x]) { if (Lx[y.fi] < x && x < Rx[y.fi]) continue; if (Ly[x] > y.fi) { minimize(Ly[x], y.fi); maximize(Ry[x], y.fi); minimize(Lx[y.fi], x); maximize(Rx[y.fi], x); ans[y.se] = '1'; cntX[x]++; break; } } if (cntX[x] == 2) continue; reverse(all(saveY[x])); for(auto &y : saveY[x]) { if (Lx[y.fi] < x && x < Rx[y.fi]) continue; minimize(Ly[x], y.fi); maximize(Ry[x], y.fi); minimize(Lx[y.fi], x); maximize(Rx[y.fi], x); ans[y.se] = '1'; cntX[x]++; break; } } cout << ans; } } void init(void) { cin >> n; REP(i, n) { cin >> p[i].x >> p[i].y; p[i].id = i; saveY[p[i].x].pb(mp(p[i].y, p[i].id)); } } void process(void) { if (Subtask12 :: check()) Subtask12 :: solve(); else Subtask6 :: solve(); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int tc = 1; // cin >> tc; while(tc--) { init(); process(); } return 0; }

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