Submission #1222478

#TimeUsernameProblemLanguageResultExecution timeMemory
1222478poat도서관 (JOI18_library)C++17
100 / 100
72 ms476 KiB
#include <bits/stdc++.h> #include <cstdio> #include <vector> #include "library.h" using namespace std; mt19937 rng(time(0)); vector<int> f[1005]; set<pair<int, int>> S; pair<int, int> getind(int ind) { for(auto i : S) { ind--; if(ind == 0) return i; } assert(0); } int ask(int m, int x, int n) { vector<int> v(n); v[x - 1] = 1; for(auto i : S) { m--; for(auto j : f[i.first]) v[j - 1] = 1; if(m == 0) break; } return Query(v); } bool fask(int a, int b, int n) { vector<int> v(n); v[a - 1] = 1; v[b - 1] = 1; return (Query(v) == 1); } void add(int ind, int x, int n) { pair<int, int> p = getind(ind); S.erase(p); if(fask(p.second, x, n)) { f[p.first].push_back(x); p.second = x; } else { f[x].push_back(x); for(auto i : f[p.first]) f[x].push_back(i); f[p.first].clear(); p.first = x; } // cout << p.first << ' ' << p.second << ' ' << x << '\n'; // exit(0); S.insert(p); } void Solve(int N) { for(int i = 0; i <= N; i++) f[i].clear(); S.clear(); vector<int> vec; for(int i = 1; i <= N; i++) vec.push_back(i); // shuffle(vec.begin(), vec.end(), rng); for(auto x : vec) { if(ask(S.size(), x, N) == S.size() + 1) { f[x].push_back(x); S.insert({x, x}); } else if(ask(S.size(), x, N) == S.size()) { int l = 0, r = S.size(); while(r - l > 1) { int m = (l + r) / 2; if(ask(m, x, N) == m) r = m; else l = m; } add(r, x, N); } else if(ask(S.size(), x, N) == S.size() - 1) { int l = 0, r = S.size(); while(r - l > 1) { int m = (l + r) / 2; if(ask(m, x, N) == m - 1) r = m; else l = m; } int i2 = r; l = 0, r--; while(r - l > 1) { int m = (l + r) / 2; if(ask(m, x, N) == m) r = m; else l = m; } int i1 = r; pair<int, int> p1 = getind(i1); pair<int, int> p2 = getind(i2); S.erase(p1); S.erase(p2); if(fask(x, p1.first, N)) { f[p1.first].swap(f[p1.second]); swap(p1.first, p1.second); reverse(f[p1.first].begin(), f[p1.first].end()); } if(fask(x, p2.second, N)) { f[p2.first].swap(f[p2.second]); swap(p2.first, p2.second); reverse(f[p2.first].begin(), f[p2.first].end()); } pair<int, int> p = {p1.first, p2.second}; f[p1.first].push_back(x); for(auto i : f[p2.first]) f[p1.first].push_back(i); f[p2.first].clear(); S.insert(p); } else assert(0); } Answer(f[S.begin()->first]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...