#include <bits/stdc++.h>
#include "library.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e3 + 2;
const int inf = 2e9;
void Solve(int n) {
vector<int> init(n), pref(n);
for (int i = 0; i < n; i++) {
init[i] = 1;
pref[i] = Query(init);
}
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
if (pref[i] > pref[i - 1]) continue;
int l = 0, r = i - 1, pos = -1, spos = -1;
while (l <= r) {
int mid = l + r >> 1;
vector<int> t(n);
for (int j = 0; j <= mid; j++) t[j] = 1;
t[i] = 1;
if (pref[mid] >= Query(t)) {
pos = mid;
r = mid - 1;
}
else l = mid + 1;
}
g[pos].push_back(i);
g[i].push_back(pos);
if (pref[i] == pref[i - 1]) continue;
l = pos + 1, r = i - 1, spos = -1;
while (l <= r) {
int mid = l + r >> 1;
vector<int> t(n);
for (int j = 0; j <= mid; j++) t[j] = 1;
t[i] = 1;
if (pref[mid] - 1 == Query(t)) {
spos = mid;
r = mid - 1;
}
else l = mid + 1;
}
g[spos].push_back(i);
g[i].push_back(spos);
}
int root = -1;
for (int i = 0; i < n; i++) if (g[i].size() == 1) root = i;
vector<int> ans;
function<void(int, int)> Dfs = [&] (int s, int e) {
ans.push_back(s + 1);
for (int u : g[s]) {
if (u == e) continue;
Dfs(u, s);
}
};
Dfs(root, -1);
Answer(ans);
}
Compilation message
library.cpp: In function 'void Solve(int)':
library.cpp:23:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | int mid = l + r >> 1;
| ~~^~~
library.cpp:38:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
300 KB |
# of queries: 1466 |
| 2 |
Correct |
12 ms |
300 KB |
# of queries: 1468 |
| 3 |
Correct |
24 ms |
300 KB |
# of queries: 1535 |
| 4 |
Correct |
27 ms |
300 KB |
# of queries: 1546 |
| 5 |
Correct |
23 ms |
296 KB |
# of queries: 1546 |
| 6 |
Correct |
14 ms |
300 KB |
# of queries: 1530 |
| 7 |
Correct |
19 ms |
308 KB |
# of queries: 1544 |
| 8 |
Correct |
22 ms |
308 KB |
# of queries: 1461 |
| 9 |
Correct |
25 ms |
292 KB |
# of queries: 1550 |
| 10 |
Correct |
11 ms |
208 KB |
# of queries: 909 |
| 11 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [5] |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
300 KB |
# of queries: 1466 |
| 2 |
Correct |
12 ms |
300 KB |
# of queries: 1468 |
| 3 |
Correct |
24 ms |
300 KB |
# of queries: 1535 |
| 4 |
Correct |
27 ms |
300 KB |
# of queries: 1546 |
| 5 |
Correct |
23 ms |
296 KB |
# of queries: 1546 |
| 6 |
Correct |
14 ms |
300 KB |
# of queries: 1530 |
| 7 |
Correct |
19 ms |
308 KB |
# of queries: 1544 |
| 8 |
Correct |
22 ms |
308 KB |
# of queries: 1461 |
| 9 |
Correct |
25 ms |
292 KB |
# of queries: 1550 |
| 10 |
Correct |
11 ms |
208 KB |
# of queries: 909 |
| 11 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [5] |
| 12 |
Halted |
0 ms |
0 KB |
- |
