#include <bits/stdc++.h>
#include "library.h"
//#include "grader.cpp"
using namespace std;
bool E[1000][1000],VIS[1000];
int CNT[1000],NN;
void DFS(int v,int L,int R,int BL){
if(VIS[v])return;
VIS[v] = 1;
for(int i = 0; i < NN; i += 1)if(E[i][v] && i >= L && i <= R && i != BL)DFS(i,L,R,BL);
}
int BS(int idx,int BL = -1){
int L = 0, R = idx - 1 -(BL != -1), mid;
while(L <= R){
if(L == R){
E[idx][L + (L >= BL && BL != -1)] = E[L + (L >= BL && BL != -1)][idx] = 1;
CNT[idx]++,CNT[L + (L >= BL && BL != -1)]++;
//cout<<L + 1 + (L >= BL && BL != -1)<<endl;
return L + (L >= BL && BL != -1);
}
//cout<<L<<' '<<R<<endl;
vector<int>F(NN,0);
mid = (L + R) / 2;
int Z = 0;
for(int i = L; i <= mid; i += 1)F[i + (BL != -1 && i >= BL)] = 1;
F[idx] = 1;
for(int i = L; i <= mid; i += 1){
//cout<<"Q: " <<i + (BL != -1 && i >= BL)<<endl;
if(!VIS[i + (BL != -1 && i >= BL)])DFS(i + (BL != -1 && i >= BL),L + (BL != -1 && L >= BL),mid + (BL != -1 && mid >= BL),BL),Z++;
}
//cout<<"Z: "<<Z<<' '<<Query(F)<<endl;
if(Z >= Query(F))R = mid;
else L = mid + 1;
for(int i = 0; i < NN; i += 1)VIS[i] = 0;
}
}
void Solve(int N)
{
NN = N;
vector<int> M(N);
M[0] = 1;
int LST = 1;
for(int i = 1; i < N; i += 1){
M[i] = 1;
int A = Query(M);
if(A <= LST){
//cout<<"Hmm: "<<i + 1<<endl;
if(A == LST)BS(i);
else{
int Q = BS(i);
//cout<<"BL: "<<Q<<endl;
BS(i,Q);
}
}
LST = A;
}
int S = 0, P = -1;
for(int i = 0; i < N; i += 1)if(CNT[i] == 1){S = i;}
vector<int> res;
while(1){
res.push_back(S + 1);
//cout<<S + 1<<' ';
for(int i = 0; i < N; i += 1)if(i != P && E[S][i]){P = S, S = i; goto a;}
break;
a:;
}
//cout<<res.size()<<endl;
Answer(res);
}
Compilation message
library.cpp: In function 'int BS(int, int)':
library.cpp:36:1: warning: control reaches end of non-void function [-Wreturn-type]
36 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
464 KB |
# of queries: 1520 |
| 2 |
Correct |
28 ms |
468 KB |
# of queries: 1504 |
| 3 |
Correct |
37 ms |
404 KB |
# of queries: 1585 |
| 4 |
Correct |
29 ms |
492 KB |
# of queries: 1583 |
| 5 |
Correct |
36 ms |
484 KB |
# of queries: 1580 |
| 6 |
Correct |
32 ms |
576 KB |
# of queries: 1587 |
| 7 |
Correct |
19 ms |
468 KB |
# of queries: 1595 |
| 8 |
Correct |
27 ms |
476 KB |
# of queries: 1509 |
| 9 |
Correct |
28 ms |
432 KB |
# of queries: 1593 |
| 10 |
Correct |
20 ms |
392 KB |
# of queries: 939 |
| 11 |
Correct |
0 ms |
208 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
208 KB |
# of queries: 1 |
| 13 |
Correct |
0 ms |
308 KB |
# of queries: 3 |
| 14 |
Correct |
1 ms |
208 KB |
# of queries: 6 |
| 15 |
Correct |
1 ms |
208 KB |
# of queries: 57 |
| 16 |
Correct |
3 ms |
208 KB |
# of queries: 130 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
464 KB |
# of queries: 1520 |
| 2 |
Correct |
28 ms |
468 KB |
# of queries: 1504 |
| 3 |
Correct |
37 ms |
404 KB |
# of queries: 1585 |
| 4 |
Correct |
29 ms |
492 KB |
# of queries: 1583 |
| 5 |
Correct |
36 ms |
484 KB |
# of queries: 1580 |
| 6 |
Correct |
32 ms |
576 KB |
# of queries: 1587 |
| 7 |
Correct |
19 ms |
468 KB |
# of queries: 1595 |
| 8 |
Correct |
27 ms |
476 KB |
# of queries: 1509 |
| 9 |
Correct |
28 ms |
432 KB |
# of queries: 1593 |
| 10 |
Correct |
20 ms |
392 KB |
# of queries: 939 |
| 11 |
Correct |
0 ms |
208 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
208 KB |
# of queries: 1 |
| 13 |
Correct |
0 ms |
308 KB |
# of queries: 3 |
| 14 |
Correct |
1 ms |
208 KB |
# of queries: 6 |
| 15 |
Correct |
1 ms |
208 KB |
# of queries: 57 |
| 16 |
Correct |
3 ms |
208 KB |
# of queries: 130 |
| 17 |
Correct |
909 ms |
1452 KB |
# of queries: 10293 |
| 18 |
Correct |
819 ms |
1260 KB |
# of queries: 10157 |
| 19 |
Correct |
876 ms |
1368 KB |
# of queries: 10273 |
| 20 |
Correct |
712 ms |
1204 KB |
# of queries: 9627 |
| 21 |
Correct |
666 ms |
1272 KB |
# of queries: 9026 |
| 22 |
Correct |
858 ms |
1320 KB |
# of queries: 10318 |
| 23 |
Correct |
789 ms |
1276 KB |
# of queries: 10264 |
| 24 |
Correct |
175 ms |
804 KB |
# of queries: 4775 |
| 25 |
Correct |
770 ms |
1360 KB |
# of queries: 10070 |
| 26 |
Correct |
670 ms |
1204 KB |
# of queries: 9420 |
| 27 |
Correct |
148 ms |
704 KB |
# of queries: 4770 |
| 28 |
Correct |
735 ms |
1276 KB |
# of queries: 8977 |
| 29 |
Correct |
731 ms |
1380 KB |
# of queries: 8967 |
| 30 |
Correct |
713 ms |
1332 KB |
# of queries: 8977 |
