제출 #831213

#제출 시각아이디문제언어결과실행 시간메모리
831213NK_Towers (NOI22_towers)C++17
75 / 100
2108 ms799448 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; for(int t = 0; t < 2; t++) { map<int, int> mp; int cur = 0; for(auto& x : A) mp[x.f]++; for(auto& x : mp) x.s = cur++; for(auto& x : A) x.f = mp[x.f], swap(x.f, x.s); } map<pi, int> IDX; for(int i = 0; i < N; i++) { // cerr << A[i].f << " " << A[i].s << " is " << i << endl; IDX[A[i]] = i; } V<vi> C(N); for(int i = 0; i < N; i++) C[A[i].s].pb(A[i].f); for(int i = 0; i < N; i++) sort(begin(C[i]), end(C[i])); V<deque<pi>> R(N); vi POS(2 * N, -1); int Q = 0; function<void(int)> update = [&](int x) { Q++; assert(Q <= 3 * N); // cerr << "UPDATE " << x << endl; if (POS[x] == -1) return; // 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; return; } if (POS[2*y] == POS[2*y+1]) { POS[x] = -1; return; // stop because same as other one } int r = C[y][POS[x]]; // row // cerr << x << " " << y << " " << dir << " " << r << endl; if (sz(R[r]) == 0) { // cerr << "ADDED TO " << r << endl; R[r].pb(mp(y, x)); return; } // 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; // cerr << "MUST UPDATE: " << i << endl; R[r].pop_back(); R[r].pb(mp(y, x)); update(i); } else R[r].pb(mp(y, x)); return; } 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; // cerr << "MUST UPDATE: " << i << endl; R[r].pop_front(); R[r].pf(mp(y, x)); update(i); } else R[r].pf(mp(y, x)); return; } POS[x] += dir; } }; vi cols; for(int i = 0; i < N; i++) { cols.pb(A[i].s); } sort(begin(cols), end(cols)); cols.erase(unique(begin(cols), end(cols)), end(cols)); for(auto& c : cols) { // cerr << c << endl; // for(auto r : C[c]) cerr << r << " "; // cerr << endl; 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 * N; i++) { int c = i / 2; if (0 <= POS[i] && POS[i] < sz(C[c])) { take.pb(mp(C[c][POS[i]], c)); // cerr << i << " " << c << " " << C[c][POS[i]] << endl; } } string ans(N, '0'); for(auto& p : take) ans[IDX[p]] = '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; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:147:7: warning: variable 'check' set but not used [-Wunused-but-set-variable]
  147 |  auto check = [&]() {
      |       ^~~~~
#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...