Submission #831215

#TimeUsernameProblemLanguageResultExecution timeMemory
831215NK_Towers (NOI22_towers)C++17
75 / 100
2100 ms627616 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; scanf("%d", &N); vpi A(N); for(auto& x : A) { scanf("%d %d", &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); // cerr << x.f << " " << x.s << endl; swap(x.f, x.s); } // cerr << endl; ROWS = sz(X); swap(ROWS, COLS); } map<ll, int> IDX; for(int i = 0; i < N; i++) { // cerr << A[i].f << " " << A[i].s << " is " << i << endl; 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])); V<deque<pi>> R(ROWS); vi POS(2 * COLS, -1); int Q = 0; vi stk; function<void(int)> update = [&](int X) { stk.pb(X); while(sz(stk)) { Q++; assert(Q <= 3 * N); int x = stk.back(); stk.pop_back(); if (POS[x] == -1) continue; // cerr << "UPDATE " << x << endl; // 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) { 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 // cerr << r << " " << y << " " << x << " " << dir << endl; if (sz(R[r]) == 0) { // cerr << "ADDED " << r << endl; R[r].pb(mp(y, x)); break; } // check if you can put it in if (R[r].back().f < y) { // sz(R[r]) == 2 put in at the back // cerr << "ADDED TO BACK " << r << endl; if (sz(R[r]) == 2) { int i = R[r].back().s; R[r].pop_back(); R[r].pb(mp(y, x)); // cerr << "MUST UPDATE " << i << endl; stk.pb(i); } else R[r].pb(mp(y, x)); break; } if (y < R[r].front().f) { // sz(R[r]) == 2 put in at the front // cerr << "ADDED TO FRONT " << r << endl; if (sz(R[r]) == 2) { int i = R[r].front().s; R[r].pop_front(); R[r].pf(mp(y, x)); // cerr << "MUST UPDATE " << i << endl; stk.pb(i); } else R[r].pf(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])) { // cerr << C[c][POS[i]] << " " << c << endl; take.pb(mp(C[c][POS[i]], c)); } } string ans(N, '0'); for(auto& p : take) { // cerr << p.f * 1LL * COLS + p.s << endl; ans[IDX[p.f * 1LL * COLS + p.s]] = '1'; } cout << ans << endl; auto check = [&]() { vi good(N); map<int, int> ROW, COL; for(int i = 0; i < N; i++) if (ans[i] == '1') { ROW[A[i].f]++; COL[A[i].s]++; } for(auto p : ROW) if (p.s > 2) assert(false); for(auto p : COL) if (p.s > 2) assert(false); for(int i = 0; i < N; i++) { if (ans[i] == '0') { for(int a = 0; a < N; a++) for(int b = 0; b < N; b++) { if (a == b) continue; if (ans[a] != '1' || ans[b] != '1') continue; if ((A[a].f != A[b].f) ^ (A[a].s != A[b].s) ^ 1) continue; int l = min(A[a].f, A[b].f), r = max(A[a].f, A[b].f); int L = min(A[a].s, A[b].s), R = max(A[a].s, A[b].s); // cerr << a << " " << b << endl; // cerr << l << " " << r << endl; // cerr << L << " " << R << endl; // cerr << endl; if (l <= A[i].f && A[i].f <= r && L <= A[i].s && A[i].s <= R) { good[i] = 1; } } } else good[i] = 1; } assert(accumulate(begin(good), end(good), 0) == N); }; // check(); return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:154:7: warning: variable 'check' set but not used [-Wunused-but-set-variable]
  154 |  auto check = [&]() {
      |       ^~~~~
Main.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  int N; scanf("%d", &N);
      |         ~~~~~^~~~~~~~~~
Main.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf("%d %d", &x.f, &x.s);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~
#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...