Submission #642060

#TimeUsernameProblemLanguageResultExecution timeMemory
642060valerikkLibrary (JOI18_library)C++17
100 / 100
306 ms336 KiB
#include <cstdio> #include <vector> #include <cassert> #include <iostream> #include "library.h" using namespace std; void Solve(int n) { if (n == 1) { Answer({1}); return; } vector<int> ends; for (int i = 0; i < n; ++i) { vector<int> a(n, 1); a[i] = 0; if (Query(a) == 1) { ends.push_back(i); } } assert(ends.size() == 2); vector<int> p(n); p[0] = ends[0]; p[n - 1] = ends[1]; vector<bool> used(n, false); used[p[0]] = true; used[p[n - 1]] = true; // cout << p[0] << " " << p[n - 1] << "\n"; int l = 0, r = n - 1; while (l + 1 < r) { vector<int> a; for (int i = 0; i < n; ++i) { if (!used[i]) a.push_back(i); } if (l + 1 == r) { p[l + 1] = a[0]; break; } int l_id = 0, r_id = 0; int sz = a.size(); for (int t = 0; (1 << t) < sz; ++t) { vector<int> v(n, 0); for (int i = 0; i < sz; ++i) { if ((i >> t) & 1) v[a[i]] = 1; } int ans00 = Query(v); v[p[l]] = 1; int ans10 = Query(v); v[p[l]] = 0; v[p[r]] = 1; int ans01 = Query(v); v[p[r]] = 0; v[p[l]] = 1; v[p[r]] = 1; int ans11 = Query(v); v[p[l]] = 0; v[p[r]] = 0; if (ans00 == ans11) { l_id += 1 << t; r_id += 1 << t; continue; } if (ans00 + 2 == ans11) { continue; } assert(ans10 != ans01); if (ans10 < ans01) { l_id += 1 << t; } else { r_id += 1 << t; } } ++l; --r; p[l] = a[l_id]; p[r] = a[r_id]; used[p[l]] = true; used[p[r]] = true; } for (int i = 0; i < n; ++i) { ++p[i]; } Answer(p); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...