# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
566671 | 2022-05-22T15:16:00 Z | two_sides | Library (JOI18_library) | C++17 | 279 ms | 336 KB |
#include <bits/stdc++.h> #include "library.h" namespace { using namespace std; const int N = 1005; bool vis[N]; } void Solve(int n) { vector<int> ans; int lo = 2, hi = n; if (n == 1) { Answer(vector<int> (1, 1)); return; } while (lo < hi) { int mi = (lo + hi) / 2; vector<int> bit(n); for (int i = 2; i <= mi; i++) bit[i - 1] = 1; int tmp = Query(bit); bit[0] = 1; if (Query(bit) > tmp) lo = mi + 1; else hi = mi; } ans.push_back(hi); ans.push_back(1); vis[1] = vis[hi] = 1; while (true) { vector<int> alive; for (int i = 1; i <= n; i++) if (!vis[i]) alive.push_back(i); lo = 0; hi = alive.size(); while (lo < hi) { int mi = (lo + hi) / 2; vector<int> bit(n); for (int i = 0; i <= mi; i++) bit[alive[i] - 1] = 1; int tmp = Query(bit); bit[ans.back() - 1] = 1; if (Query(bit) > tmp) lo = mi + 1; else hi = mi; } if (hi < alive.size()) { ans.push_back(alive[hi]); vis[alive[hi]] = 1; } else break; } reverse(ans.begin(), ans.end()); while (true) { vector<int> alive; for (int i = 1; i <= n; i++) if (!vis[i]) alive.push_back(i); lo = 0; hi = alive.size(); while (lo < hi) { int mi = (lo + hi) / 2; vector<int> bit(n); for (int i = 0; i <= mi; i++) bit[alive[i] - 1] = 1; int tmp = Query(bit); bit[ans.back() - 1] = 1; if (Query(bit) > tmp) lo = mi + 1; else hi = mi; } if (hi < alive.size()) { ans.push_back(alive[hi]); vis[alive[hi]] = 1; } else break; } Answer(ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 208 KB | # of queries: 2412 |
2 | Correct | 37 ms | 208 KB | # of queries: 2372 |
3 | Correct | 32 ms | 208 KB | # of queries: 2526 |
4 | Correct | 32 ms | 208 KB | # of queries: 2556 |
5 | Correct | 28 ms | 208 KB | # of queries: 2550 |
6 | Correct | 32 ms | 304 KB | # of queries: 2540 |
7 | Correct | 35 ms | 208 KB | # of queries: 2526 |
8 | Correct | 29 ms | 208 KB | # of queries: 2430 |
9 | Correct | 30 ms | 208 KB | # of queries: 2508 |
10 | Correct | 23 ms | 208 KB | # of queries: 1468 |
11 | Correct | 1 ms | 208 KB | # of queries: 0 |
12 | Correct | 0 ms | 208 KB | # of queries: 0 |
13 | Correct | 0 ms | 208 KB | # of queries: 4 |
14 | Correct | 1 ms | 208 KB | # of queries: 12 |
15 | Correct | 2 ms | 208 KB | # of queries: 90 |
16 | Correct | 3 ms | 208 KB | # of queries: 200 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 208 KB | # of queries: 2412 |
2 | Correct | 37 ms | 208 KB | # of queries: 2372 |
3 | Correct | 32 ms | 208 KB | # of queries: 2526 |
4 | Correct | 32 ms | 208 KB | # of queries: 2556 |
5 | Correct | 28 ms | 208 KB | # of queries: 2550 |
6 | Correct | 32 ms | 304 KB | # of queries: 2540 |
7 | Correct | 35 ms | 208 KB | # of queries: 2526 |
8 | Correct | 29 ms | 208 KB | # of queries: 2430 |
9 | Correct | 30 ms | 208 KB | # of queries: 2508 |
10 | Correct | 23 ms | 208 KB | # of queries: 1468 |
11 | Correct | 1 ms | 208 KB | # of queries: 0 |
12 | Correct | 0 ms | 208 KB | # of queries: 0 |
13 | Correct | 0 ms | 208 KB | # of queries: 4 |
14 | Correct | 1 ms | 208 KB | # of queries: 12 |
15 | Correct | 2 ms | 208 KB | # of queries: 90 |
16 | Correct | 3 ms | 208 KB | # of queries: 200 |
17 | Correct | 238 ms | 296 KB | # of queries: 17182 |
18 | Correct | 279 ms | 292 KB | # of queries: 17004 |
19 | Correct | 247 ms | 208 KB | # of queries: 17210 |
20 | Correct | 232 ms | 296 KB | # of queries: 16048 |
21 | Correct | 239 ms | 336 KB | # of queries: 15088 |
22 | Correct | 250 ms | 208 KB | # of queries: 17146 |
23 | Correct | 178 ms | 296 KB | # of queries: 17192 |
24 | Correct | 80 ms | 292 KB | # of queries: 7856 |
25 | Correct | 262 ms | 292 KB | # of queries: 16782 |
26 | Correct | 224 ms | 296 KB | # of queries: 15628 |
27 | Correct | 89 ms | 300 KB | # of queries: 7812 |
28 | Correct | 235 ms | 288 KB | # of queries: 17972 |
29 | Correct | 213 ms | 208 KB | # of queries: 17952 |
30 | Correct | 252 ms | 292 KB | # of queries: 17972 |