Submission #1217962

#TimeUsernameProblemLanguageResultExecution timeMemory
1217962The_SamuraiLibrary (JOI18_library)C++20
100 / 100
121 ms424 KiB
#include "bits/stdc++.h" #include "library.h" using namespace std; void Solve(int n) { vector<int> v = {1}, left; for (int i = 2; i <= n; i++) { vector<int> m(n); m[i - 1] = true; for (int x: v) m[x - 1] = true; if (Query(m) == 1) { if (v.size() == 1) v.emplace_back(i); else { m[v.back() - 1] = false; if (Query(m) == 1) v.insert(v.begin(), i); else v.emplace_back(i); } } else { left.emplace_back(i); } } // for (int x: v) cout << x << ' '; // cout << endl; for (int t = 0; t < 2; t++) { while (!left.empty()) { int lx = 0, rx = left.size() - 1, best = -1; while (lx <= rx) { int mid = (lx + rx) >> 1; vector<int> m(n); for (int x: v) m[x - 1] = 1; for (int i = 0; i <= mid; i++) m[left[i] - 1] = 1; int old = Query(m); m[v.back() - 1] = 0; if (old != Query(m)) { best = mid; rx = mid - 1; } else { lx = mid + 1; } } if (best == -1) break; v.emplace_back(left[best]); left.erase(left.begin() + best); } reverse(v.begin(), v.end()); } Answer(v); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...