| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1034322 |
2024-07-25T12:17:02 Z |
juicy |
Library (JOI18_library) |
C++17 |
|
213 ms |
432 KB |
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
void Solve(int N) {
vector<bool> vs(N);
vector<int> M(N);
auto qry = [&](vector<int> &que) {
fill(M.begin(), M.end(), 0);
for (int x : que) {
M[x - 1] = 1;
}
return Query(M);
};
auto check = [&](vector<int> &que, int x) {
int a = qry(que);
que.push_back(x);
int b = qry(que);
return b <= a;
};
auto search = [&](int x) {
vector<int> cands;
for (int i = 0; i < N; ++i) {
if (!vs[i]) {
cands.push_back(i + 1);
}
}
if (!cands.size()) {
return 0;
}
int l = 0, r = int(cands.size()) - 1, res = -1;
while (l <= r) {
int md = (l + r) / 2;
vector<int> que;
for (int i = 0; i <= md; ++i) {
que.push_back(cands[i]);
}
if (check(que, x)) {
res = md;
r = md - 1;
} else {
l = md + 1;
}
}
if (res != -1) {
vs[cands[res] - 1] = 1;
assert(0 < cands[res] && cands[res] <= N);
return cands[res];
}
return 0;
};
if (N == 1) {
Answer({1});
return;
}
deque<int> dq;
vs[0] = 1;
int l = 1, r = search(1);
dq.push_front(l);
dq.push_back(r);
int cnt = N - 2;
while (1) {
l = search(l);
if (l == 0) {
break;
}
dq.push_front(l);
--cnt;
}
while (cnt > 0) {
r = search(r);
dq.push_back(r);
--cnt;
}
Answer(vector<int>(dq.begin(), dq.end()));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
344 KB |
# of queries: 2410 |
| 2 |
Correct |
13 ms |
344 KB |
# of queries: 2380 |
| 3 |
Correct |
21 ms |
344 KB |
# of queries: 2522 |
| 4 |
Correct |
22 ms |
432 KB |
# of queries: 2538 |
| 5 |
Correct |
19 ms |
432 KB |
# of queries: 2526 |
| 6 |
Correct |
19 ms |
344 KB |
# of queries: 2526 |
| 7 |
Correct |
36 ms |
432 KB |
# of queries: 2524 |
| 8 |
Correct |
22 ms |
344 KB |
# of queries: 2424 |
| 9 |
Correct |
17 ms |
344 KB |
# of queries: 2502 |
| 10 |
Correct |
13 ms |
344 KB |
# of queries: 1484 |
| 11 |
Correct |
0 ms |
344 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
344 KB |
# of queries: 2 |
| 13 |
Correct |
0 ms |
344 KB |
# of queries: 4 |
| 14 |
Correct |
0 ms |
344 KB |
# of queries: 12 |
| 15 |
Correct |
1 ms |
344 KB |
# of queries: 86 |
| 16 |
Correct |
2 ms |
344 KB |
# of queries: 190 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
344 KB |
# of queries: 2410 |
| 2 |
Correct |
13 ms |
344 KB |
# of queries: 2380 |
| 3 |
Correct |
21 ms |
344 KB |
# of queries: 2522 |
| 4 |
Correct |
22 ms |
432 KB |
# of queries: 2538 |
| 5 |
Correct |
19 ms |
432 KB |
# of queries: 2526 |
| 6 |
Correct |
19 ms |
344 KB |
# of queries: 2526 |
| 7 |
Correct |
36 ms |
432 KB |
# of queries: 2524 |
| 8 |
Correct |
22 ms |
344 KB |
# of queries: 2424 |
| 9 |
Correct |
17 ms |
344 KB |
# of queries: 2502 |
| 10 |
Correct |
13 ms |
344 KB |
# of queries: 1484 |
| 11 |
Correct |
0 ms |
344 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
344 KB |
# of queries: 2 |
| 13 |
Correct |
0 ms |
344 KB |
# of queries: 4 |
| 14 |
Correct |
0 ms |
344 KB |
# of queries: 12 |
| 15 |
Correct |
1 ms |
344 KB |
# of queries: 86 |
| 16 |
Correct |
2 ms |
344 KB |
# of queries: 190 |
| 17 |
Correct |
198 ms |
344 KB |
# of queries: 17162 |
| 18 |
Correct |
184 ms |
344 KB |
# of queries: 16984 |
| 19 |
Correct |
157 ms |
344 KB |
# of queries: 17198 |
| 20 |
Correct |
170 ms |
344 KB |
# of queries: 16018 |
| 21 |
Correct |
163 ms |
344 KB |
# of queries: 15060 |
| 22 |
Correct |
202 ms |
344 KB |
# of queries: 17178 |
| 23 |
Correct |
213 ms |
344 KB |
# of queries: 17188 |
| 24 |
Correct |
72 ms |
344 KB |
# of queries: 7868 |
| 25 |
Correct |
197 ms |
344 KB |
# of queries: 16720 |
| 26 |
Correct |
166 ms |
344 KB |
# of queries: 15608 |
| 27 |
Correct |
80 ms |
344 KB |
# of queries: 7796 |
| 28 |
Correct |
174 ms |
344 KB |
# of queries: 15994 |
| 29 |
Correct |
149 ms |
344 KB |
# of queries: 15976 |
| 30 |
Correct |
184 ms |
344 KB |
# of queries: 15994 |
