#include <bits/stdc++.h> using namespace std; #define TASK "SLAMP" #define all(x) (x).begin(), (x).end() typedef long long ll; typedef pair<int, int> ii; const int MAX_N = 1e6; const int MOD = (int)1e9 + 7; const int INF = 1e9; template<class X, class Y> bool maximize(X &x, const Y &y) { if (x >= y) return false; x = y; return true; }; template<class X, class Y> bool minimize(X &x, const Y &y) { if (x <= y) return false; x = y; return true; }; int n; ii a[MAX_N + 5]; namespace SUBTASK_2 { const int N = 16; const int V = 1e6; int cntX[V + 5], cntY[V + 5]; bool ans[N + 5]; bool checkNS(int mask, int i) { bool N = false, S = false; for (int j = 1; j <= n; j++) { if (j == i) continue; if (mask >> (j - 1) & 1) { if (a[j].second == a[i].second) { if (a[j].first < a[i].first) N = true; if (a[j].first > a[i].first) S = true; }; }; }; return N && S; }; bool checkWE(int mask, int i) { bool W = false, E = false; for (int j = 1; j <= n; j++) { if (j == i) continue; if (mask >> (j - 1) & 1) { if (a[j].first == a[i].first) { if (a[j].second < a[i].second) W = true; if (a[j].second > a[i].second) E = true; }; }; }; return W && E; }; void Solve() { int res = 0; for (int mask = 0; mask < (1 << n); mask++) { for (int haha = mask; haha > 0; haha ^= haha & (-haha)) { int i = __builtin_ctz(haha) + 1; int x = a[i].first, y = a[i].second; cntX[x]++, cntY[y]++; }; bool valid = true; for (int i = 1; i <= n; i++) { int x = a[i].first, y = a[i].second; if (cntX[x] > 2) valid = false; if (cntY[y] > 2) valid = false; if (!(mask >> (i - 1) & 1)) { if (!checkNS(mask, i) && !checkWE(mask, i)) valid = false; }; if (!valid) break; }; for (int haha = mask; haha > 0; haha ^= haha & (-haha)) { int i = __builtin_ctz(haha) + 1; int x = a[i].first, y = a[i].second; cntX[x]--, cntY[y]--; }; if (valid) { res = mask; break; }; }; for (int i = 0; i < n; i++) { cout << (res >> i & 1); }; }; }; namespace SUBTASK_5 { const int N = MAX_N; const int V = 1e6; int leftCol[V + 5], rightCol[V + 5], topRow[V + 5], botRow[V + 5]; int last[V + 5], cntX[V + 5], cntY[V + 5]; bool used[N + 5]; vector<int> col[V + 5]; bool firstInRow(int idx) { return leftCol[idx] == a[idx].second; }; bool lastInRow(int idx) { return rightCol[idx] == a[idx].second; }; bool firstInCol(int idx) { return col[a[idx].second].front() == idx; }; bool lastInCol(int idx) { return col[a[idx].second].back() == idx; }; void update(int idx) { int x = a[idx].first, y = a[idx].second; used[idx] = true; cntX[x]++, cntY[y]++; assert(cntX[x] <= 2); assert(cntY[y] <= 2); }; void Solve() { for (int i = 1; i <= n; i++) { col[a[i].second].push_back(i); }; for (int y = 1; y <= V; y++) { sort(all(col[y]), [&](int i, int j) { return a[i].first < a[j].first; }); }; for (int i = 1; i <= n; i++) leftCol[i] = V + 1, rightCol[i] = 0; for (int x = 1; x <= V; x++) last[x] = V + 1; for (int y = 1; y <= V; y++) { for (int idx : col[y]) { int x = a[idx].first; minimize(last[x], y); minimize(leftCol[idx], last[x]); }; }; for (int x = 1; x <= V; x++) last[x] = 0; for (int y = V; y >= 1; y--) { for (int idx : col[y]) { int x = a[idx].first; maximize(last[x], y); maximize(rightCol[idx], last[x]); }; }; for (int i = 1; i <= n; i++) used[i] = false; for (int y = 1; y <= V; y++) { if (col[y].empty()) continue; for (int idx : col[y]) { if (firstInRow(idx) && firstInCol(idx)) { update(idx); } else if (lastInRow(idx) && lastInCol(idx)) { update(idx); } else if (lastInRow(idx) && firstInCol(idx)) { update(idx); } else if (firstInRow(idx) && lastInCol(idx)) { update(idx); }; }; }; for (int y = 1; y <= V; y++) { if (col[y].empty()) continue; if (cntY[y] == 2) continue; int highestRow = -1; int lowestRow = -1; for (int idx : col[y]) { if (used[idx]) continue; int x = a[idx].first, y = a[idx].second; if (cntX[x] < 2) highestRow = idx; if (cntX[x] < 2 && lowestRow == -1) lowestRow = idx; }; if (highestRow != -1) update(highestRow); if (lowestRow != -1 && lowestRow != highestRow) update(lowestRow); // cout << y << endl; }; for (int i = 1; i <= n; i++) { cout << used[i]; }; }; }; void checkAns() { ios_base::sync_with_stdio(0); cin.tie(0); const int NUM_TEST = 200; int tc = 0; system("g++ " TASK ".gentest.CPP -o " TASK ".gentest -std=c++14 -O2 -Wall -Wextra"); while (tc < NUM_TEST) { system(TASK ".gentest > " TASK ".INP"); if (fopen(TASK ".INP", "r")) { freopen(TASK ".INP", "r", stdin); freopen(TASK ".OUT", "w", stdout); }; // assert(SUBTASK_1::ans == SUBTASK_2::ans) cerr << ++tc << ": PASSED\n"; }; exit(0); }; int main() { // checkAns(); ios_base::sync_with_stdio(0); cin.tie(0); if (fopen(TASK ".INP", "r")) { freopen(TASK ".INP", "r", stdin); freopen(TASK ".OUT", "w", stdout); }; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i].first >> a[i].second; }; if (n <= 16) return SUBTASK_2::Solve(), 0; // SUBTASK_2::Solve(); // cout << endl; SUBTASK_5::Solve(); };

Main.cpp: In function 'void checkAns()':
Main.cpp:211:11: warning: ignoring return value of 'int system(const char*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  211 |     system("g++ " TASK ".gentest.CPP -o " TASK ".gentest -std=c++14 -O2 -Wall -Wextra");
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:214:15: warning: ignoring return value of 'int system(const char*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  214 |         system(TASK ".gentest > " TASK ".INP");
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:217:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |             freopen(TASK ".INP", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:218:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  218 |             freopen(TASK ".OUT", "w", stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:235:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  235 |         freopen(TASK ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:236:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  236 |         freopen(TASK ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~