#include<bits/stdc++.h> using namespace std; void local() { #define taskname "SLAMP" if (fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } } #define ll long long #define fi first #define se second #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); template<class X, class Y> bool mini(X &a, const Y &b) {return (a > b) ? a = b, true : false;} template<class X, class Y> bool maxi(X &a, const Y &b) {return (a < b) ? a = b, true : false;} const int N = 1e6 + 5; int n; pair<int, int> a[N]; int ma[N], mi[N]; int cnt[N]; bitset<N> cur; bool pls_check(bitset<N>& use) { bool state = true; for(int i = 1; i <= n; i++) cur[i] = false; for(int i = 1; i <= n; i++) { if(use[i]) { maxi(ma[a[i].fi], a[i].se); mini(mi[a[i].fi], a[i].se); cnt[a[i].fi]++; if(cnt[a[i].fi] > 2) state = false; } } for(int i = 1; i <= n; i++) if(mi[a[i].fi] <= a[i].se && a[i].se <= ma[a[i].fi]) cur[i] = true; for(int i = 1; i <= n; i++) { ma[a[i].fi] = -1e9; mi[a[i].fi] = 1e9; cnt[a[i].fi] = 0; } for(int i = 1; i <= n; i++) { if(use[i]) { maxi(ma[a[i].se], a[i].fi); mini(mi[a[i].se], a[i].fi); cnt[a[i].se]++; if(cnt[a[i].se] > 2) state = false; } } for(int i = 1; i <= n; i++) if(mi[a[i].se] <= a[i].fi && a[i].fi <= ma[a[i].se]) cur[i] = true; for(int i = 1; i <= n; i++) { ma[a[i].se] = -1e9; mi[a[i].se] = 1e9; cnt[a[i].se] = 0; } for(int i = 1; i <= n; i++) if(!cur[i]) state = false; return state; } namespace sub12 { bool check() { return n <= 16; } bool ok = false; bitset<N> ans, cur, use; void dq(int i) { if(i > n) { if(pls_check(use)) { ans = use; } return; } dq(i + 1); use[i] = true; dq(i + 1); use[i] = false; } void solve() { for(int i = 1; i < N; i++) ma[i] = -1e9, mi[i] = 1e9, cnt[i] = 0; dq(1); for(int i = 1; i <= n; i++) cout << ans[i]; } } namespace sub6 { vector<int> lst[N]; vector<pair<int, int>> val[N]; bool cmp(int x, int y) { return a[x].se < a[y].se; } bitset<N> ans; int lb[N]; void solve_up() { for(int i = 1; i < N; i++) { if(val[i].size() < 3) continue; sort(val[i].begin(), val[i].end()); swap(val[i][1], val[i].back()); vector<pair<int, int>> remain_lst; while(val[i].size() > 2) { int x, id; tie(x, id) = val[i].back(); val[i].pop_back(); id++; if(id == lst[x].size()) { remain_lst.emplace_back(x, id - 1); } else { ans[lst[x][id - 1]] = false; if(id + 1 < lst[x].size()) { lb[x] = id; val[a[lst[x][id]].se].emplace_back(x, id); ans[lst[x][id]] = true; } } } while(!remain_lst.empty()) { val[i].emplace_back(remain_lst.back()); remain_lst.pop_back(); } } } void solve_down() { for(int i = N - 1; i > 0; i--) { if(val[i].size() < 3) continue; sort(val[i].begin(), val[i].end()); swap(val[i][1], val[i].back()); while(val[i].size() > 2) { int x, id; tie(x, id) = val[i].back(); val[i].pop_back(); ans[lst[x][id]] = false; id--; if(id > lb[x]) { val[a[lst[x][id]].se].emplace_back(x, id); ans[lst[x][id]] = true; } } } } void solve() { for(int i = 1; i <= n; i++) { lst[a[i].fi].emplace_back(i); } for(int i = 1; i < N; i++) { if(lst[i].empty()) continue; sort(lst[i].begin(), lst[i].end(), cmp); vector<int> nlst; for(int j = 0; j < lst[i].size(); j++) { if(nlst.empty() || a[nlst.back()].se != a[lst[i][j]].se) { nlst.emplace_back(lst[i][j]); } } lst[i] = nlst; val[a[lst[i][0]].se].emplace_back(i, 0); ans[lst[i][0]] = true; if(a[lst[i][0]].se != a[lst[i].back()].se) { val[a[lst[i].back()].se].emplace_back(i, lst[i].size() - 1); ans[lst[i].back()] = true; } } solve_up(); solve_down(); //cout << pls_check(ans); //cout << "hi " << pls_check(ans) << '\n'; for(int i = 1; i <= n; i++) cout << ans[i]; } } int main() { fastio; local(); cin >> n; for(int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se; sub6::solve(); }

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