#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include "library.h"
using namespace std;
vector <int> asks[1024];
int range[2048][2];
int M;
void make_ask(int l, int r,int index){///search adjacent within this range
int mid=(l+r)/2;
range[index][0]=l;
range[index][1]=mid;
for(int i=0;i<M;i++){
if(i>=l&&i<=mid){
asks[index].push_back(1);
}else{
asks[index].push_back(0);
}
}
if(l==mid){//ifr-l=1
range[index*2+1][0]=l;
range[index*2+1][1]=mid;
range[index*2+2][0]=mid+1;
range[index*2+2][1]=r;
return;
}
make_ask(l,mid,index*2+1);
if(r==mid+1){//ifr-l=2
range[index*2+2][0]=mid+1;
range[index*2+2][1]=r;
return;
}
make_ask(mid+1,r,index*2+2);
}
void Solve(int N){
M=N;
vector <int> adjacent[N];
make_ask(0,N,0);
// int s=0;
// while(asks[s].size()>0){
// for(int k=0;k<M;k++){
// cout<<asks[s][k]<<' ';
// }
// s++;
// cout<<endl;
// }
for(int i=0;i<N;i++){
while(adjacent[i].size()<2){
int index=0;
while(asks[index].size()>0){//at most 10 steps so 20 queries
int with,without;
if(range[index][0]==i&&range[index][1]==i){index=index*2+2;continue;}
if(adjacent[i].size()==1){
if(range[index][0]==adjacent[i][0]&&range[index][1]==adjacent[i][0]){index=index*2+2;continue;}//without is less than with
if(adjacent[i][0]-i==1&&range[index][1]==adjacent[i][0]&&range[index][0]==i){index=index*2+2;continue;}
if(adjacent[i][0]-i==-1&&range[index][0]==adjacent[i][0]&&range[index][1]==i){index=index*2+2;continue;}
asks[index][adjacent[i][0]]=0;
}
asks[index][i]=0;
// for(int k=0;k<M;k++){
// cout<<asks[index][k]<<' ';
// }
// cout<<endl<<i<<endl;
// cout<<i<<' '<<range[index][0]<<' '<<range[index][1]<<endl;
without=Query(asks[index]);
asks[index][i]=1;
with=Query(asks[index]);
if(range[index][0]<=i&&range[index][1]>=i){
asks[index][i]=1;
}else{
asks[index][i]=0;
}
if(adjacent[i].size()==1&&range[index][0]<=adjacent[i][0]&&range[index][1]>=adjacent[i][0]){
asks[index][adjacent[i][0]]=1;
}
if(without>=with){
index=index*2+1;// adjacent within first half
}else{
index=index*2+2;
}
}
if(range[index][0]==N){
adjacent[i].push_back(N);
}else{
adjacent[i].push_back(range[index][0]);
adjacent[range[index][0]].push_back(i);
}
}
}
int corner;
for(corner=0;corner<N;corner++){
if(adjacent[corner][0]==N||adjacent[corner][1]==N){break;}
}
vector <int> finish(N,0);
int prev=N;
for(int i=0;i<N;i++){
finish[i]=corner+1;
// cout<<adjacent[i][0]<<' '<<adjacent[i][1]<<endl;
if(adjacent[corner][0]==prev){
prev=corner;
corner=adjacent[prev][1];
}else{
prev=corner;
corner=adjacent[prev][0];
}
}
Answer(finish);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
456 KB |
# of queries: 2954 |
| 2 |
Correct |
62 ms |
456 KB |
# of queries: 2950 |
| 3 |
Correct |
61 ms |
516 KB |
# of queries: 3100 |
| 4 |
Correct |
48 ms |
512 KB |
# of queries: 3092 |
| 5 |
Correct |
60 ms |
528 KB |
# of queries: 3098 |
| 6 |
Correct |
57 ms |
516 KB |
# of queries: 3102 |
| 7 |
Correct |
57 ms |
456 KB |
# of queries: 3106 |
| 8 |
Correct |
31 ms |
516 KB |
# of queries: 2954 |
| 9 |
Correct |
71 ms |
512 KB |
# of queries: 3082 |
| 10 |
Correct |
33 ms |
436 KB |
# of queries: 1822 |
| 11 |
Correct |
1 ms |
200 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
200 KB |
# of queries: 2 |
| 13 |
Correct |
1 ms |
200 KB |
# of queries: 8 |
| 14 |
Correct |
1 ms |
200 KB |
# of queries: 18 |
| 15 |
Correct |
3 ms |
200 KB |
# of queries: 124 |
| 16 |
Correct |
3 ms |
200 KB |
# of queries: 266 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
456 KB |
# of queries: 2954 |
| 2 |
Correct |
62 ms |
456 KB |
# of queries: 2950 |
| 3 |
Correct |
61 ms |
516 KB |
# of queries: 3100 |
| 4 |
Correct |
48 ms |
512 KB |
# of queries: 3092 |
| 5 |
Correct |
60 ms |
528 KB |
# of queries: 3098 |
| 6 |
Correct |
57 ms |
516 KB |
# of queries: 3102 |
| 7 |
Correct |
57 ms |
456 KB |
# of queries: 3106 |
| 8 |
Correct |
31 ms |
516 KB |
# of queries: 2954 |
| 9 |
Correct |
71 ms |
512 KB |
# of queries: 3082 |
| 10 |
Correct |
33 ms |
436 KB |
# of queries: 1822 |
| 11 |
Correct |
1 ms |
200 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
200 KB |
# of queries: 2 |
| 13 |
Correct |
1 ms |
200 KB |
# of queries: 8 |
| 14 |
Correct |
1 ms |
200 KB |
# of queries: 18 |
| 15 |
Correct |
3 ms |
200 KB |
# of queries: 124 |
| 16 |
Correct |
3 ms |
200 KB |
# of queries: 266 |
| 17 |
Runtime error |
12 ms |
8604 KB |
Execution killed with signal 11 |
| 18 |
Halted |
0 ms |
0 KB |
- |
