Submission #831220

#TimeUsernameProblemLanguageResultExecution timeMemory
831220NK_Towers (NOI22_towers)C++17
100 / 100
1450 ms133816 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define pb push_back #define pf push_front #define mp make_pair #define f first #define s second #define sz(x) int(x.size()) template<class T> using V = vector<T>; using pi = pair<int, int>; using vi = V<int>; using vpi = V<pi>; using ll = long long; using pl = pair<ll, ll>; using vpl = V<pl>; using vl = V<ll>; using db = long double; template<class T> using pq = priority_queue<T, V<T>, greater<T>>; const int MOD = 1e9 + 7; const ll INFL = ll(1e16) + 10; int main() { cin.tie(0)->sync_with_stdio(0); int N; cin >> N; vpi A(N); for(auto& x : A) { cin >> x.f >> x.s; } int ROWS = 0, COLS = 0; for(int t = 0; t < 2; t++) { vi X; for(auto& x : A) X.pb(x.f); sort(begin(X), end(X)); // X.erase(unique(begin(X), end(X)), end(X)); for(auto& x : A) { x.f = lower_bound(begin(X), end(X), x.f) - begin(X); swap(x.f, x.s); } ROWS = sz(X); swap(ROWS, COLS); } unordered_map<ll, int> IDX; for(int i = 0; i < N; i++) { IDX[A[i].f * 1LL * COLS + A[i].s] = i; } V<vi> C(COLS); for(int i = 0; i < N; i++) C[A[i].s].pb(A[i].f); for(int i = 0; i < COLS; i++) sort(begin(C[i]), end(C[i])); const pi EMP = mp(-1, -1); vpi RF(ROWS, EMP); vpi RB(ROWS, EMP); vi POS(2 * COLS, -1); int Q = 0; vi stk; function<void(int)> update = [&](int X) { stk.pb(X); while(sz(stk)) { int x = stk.back(); stk.pop_back(); if (POS[x] == -1) continue; // 2*y+c => y is col # and c is dir (0 - dwn (+1), 1 - up (-1)); int y = x / 2, dir = (x % 2 ? -1 : +1); while(1) { Q++; assert(Q <= 5 * N); if (POS[x] < 0 || POS[x] >= sz(C[y])) { POS[x] = -1; break; } if (POS[2*y] == POS[2*y+1]) { POS[x] = -1; break; // stop because same as other one } int r = C[y][POS[x]]; // row // check if you can put it in if (RB[r] == EMP || RB[r].f < y) { // sz(R[r]) == 2 put in at the back if (RB[r] != EMP) { int i = RB[r].s; RB[r] = mp(y, x); stk.pb(i); } else RB[r] = mp(y, x); break; } if (RF[r] == EMP || y < RF[r].f) { // sz(R[r]) == 2 put in at the front if (RF[r] != EMP) { int i = RF[r].s; RF[r] = mp(y, x); stk.pb(i); } else RF[r] = mp(y, x); break; } POS[x] += dir; } } }; for(int c = 0; c < COLS; c++) { POS[2 * c] = 0; update(2 * c); POS[2 * c + 1] = sz(C[c]) - 1; update(2 * c + 1); } vpi take; for(int i = 0; i < 2 * COLS; i++) { int c = i / 2; if (0 <= POS[i] && POS[i] < sz(C[c])) { take.pb(mp(C[c][POS[i]], c)); } } string ans(N, '0'); for(auto& p : take) { ans[IDX[p.f * 1LL * COLS + p.s]] = '1'; } cout << ans << nl; // cerr << Q << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...