#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x.size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;
#include<library.h>
vector<int> Q(1001, 0);
int ind = 0;
int n;
int edge = 0;
vector<int> adj[1001];
int bin(int l, int r, int v, bool eq = true){
int ret = -1;
while(l <= r){
int mid = (l + r) / 2;
vector<int> arr(n, 0);
for(int i = 0; i <= mid; i++)arr[i] = 1;
for(int i = mid + 1; i < n; i++)arr[i] = 0;
arr[v] = 1;
if((eq && Query(arr) <= Q[mid]) || (!eq && Query(arr) < Q[mid])){
ret = mid;
r = mid - 1;
}
else{
l = mid + 1;
}
}
return ret;
}
void Solve(int N){
n = N;
vector<int> arr(n, 0);
for(;ind < n; ind++){
arr[ind] = 1;
Q[ind] = Query(arr);
if(ind != 0 && Q[ind] <= Q[ind - 1]){
int x = bin(0, ind - 1, ind, true);
adj[x].pb(ind);
adj[ind].pb(x);
edge++;
x = bin(x + 1, ind - 1, ind, false);
if(x != -1){
edge++;
adj[x].pb(ind);
adj[ind].pb(x);
}
}
}
int root = 0;
while(sz(adj[root]) == 2)root++;
vector<int> ans;
int x = root;
assert(root < n);
assert(edge == n - 1);
if(n == 1){
ans.pb(1);
Answer(ans);
return;
}
for(int i = 0; i < n; i++){
assert(sz(adj[x]));
if(adj[x].size() == 1){
ans.pb(x+1);
x = adj[x][0];
}
else if(sz(adj[x]) == 2){
if(ans.back()-1 == adj[x][0]){
ans.pb(x+1);
x = adj[x][1];
}
else if(ans.back()-1 == adj[x][1]){
ans.pb(x+1);
x = adj[x][0];
}
else assert(0);
}
else assert(0);
}
Answer(ans);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
36 ms |
376 KB |
# of queries: 1758 |
| 2 |
Correct |
37 ms |
348 KB |
# of queries: 1843 |
| 3 |
Correct |
32 ms |
248 KB |
# of queries: 1878 |
| 4 |
Correct |
36 ms |
248 KB |
# of queries: 1957 |
| 5 |
Correct |
44 ms |
348 KB |
# of queries: 1917 |
| 6 |
Correct |
36 ms |
248 KB |
# of queries: 1933 |
| 7 |
Correct |
34 ms |
248 KB |
# of queries: 1934 |
| 8 |
Correct |
43 ms |
376 KB |
# of queries: 1826 |
| 9 |
Correct |
38 ms |
376 KB |
# of queries: 1920 |
| 10 |
Correct |
21 ms |
376 KB |
# of queries: 1076 |
| 11 |
Correct |
5 ms |
248 KB |
# of queries: 1 |
| 12 |
Correct |
5 ms |
248 KB |
# of queries: 3 |
| 13 |
Correct |
5 ms |
376 KB |
# of queries: 6 |
| 14 |
Correct |
5 ms |
248 KB |
# of queries: 9 |
| 15 |
Correct |
6 ms |
248 KB |
# of queries: 65 |
| 16 |
Correct |
8 ms |
376 KB |
# of queries: 159 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
36 ms |
376 KB |
# of queries: 1758 |
| 2 |
Correct |
37 ms |
348 KB |
# of queries: 1843 |
| 3 |
Correct |
32 ms |
248 KB |
# of queries: 1878 |
| 4 |
Correct |
36 ms |
248 KB |
# of queries: 1957 |
| 5 |
Correct |
44 ms |
348 KB |
# of queries: 1917 |
| 6 |
Correct |
36 ms |
248 KB |
# of queries: 1933 |
| 7 |
Correct |
34 ms |
248 KB |
# of queries: 1934 |
| 8 |
Correct |
43 ms |
376 KB |
# of queries: 1826 |
| 9 |
Correct |
38 ms |
376 KB |
# of queries: 1920 |
| 10 |
Correct |
21 ms |
376 KB |
# of queries: 1076 |
| 11 |
Correct |
5 ms |
248 KB |
# of queries: 1 |
| 12 |
Correct |
5 ms |
248 KB |
# of queries: 3 |
| 13 |
Correct |
5 ms |
376 KB |
# of queries: 6 |
| 14 |
Correct |
5 ms |
248 KB |
# of queries: 9 |
| 15 |
Correct |
6 ms |
248 KB |
# of queries: 65 |
| 16 |
Correct |
8 ms |
376 KB |
# of queries: 159 |
| 17 |
Correct |
359 ms |
376 KB |
# of queries: 12754 |
| 18 |
Correct |
326 ms |
504 KB |
# of queries: 12528 |
| 19 |
Correct |
330 ms |
504 KB |
# of queries: 12443 |
| 20 |
Correct |
316 ms |
376 KB |
# of queries: 11640 |
| 21 |
Correct |
288 ms |
376 KB |
# of queries: 11103 |
| 22 |
Correct |
322 ms |
376 KB |
# of queries: 12490 |
| 23 |
Correct |
363 ms |
380 KB |
# of queries: 12667 |
| 24 |
Correct |
116 ms |
248 KB |
# of queries: 5886 |
| 25 |
Correct |
372 ms |
504 KB |
# of queries: 12374 |
| 26 |
Correct |
342 ms |
376 KB |
# of queries: 11502 |
| 27 |
Correct |
111 ms |
244 KB |
# of queries: 5690 |
| 28 |
Correct |
324 ms |
376 KB |
# of queries: 9977 |
| 29 |
Correct |
303 ms |
376 KB |
# of queries: 9966 |
| 30 |
Correct |
306 ms |
376 KB |
# of queries: 9977 |
