#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);
#include "library.h"
int n;
int mode;
int x[1111], y[1111], id[1111];
int root(int i){
return !id[i] ? i : id[i]=root(id[i]);
}
void join(int i,int j){
if((i=root(i))==(j=root(j))) return;
id[i]=j;
}
int tim(const vector<int>&q,int mode=1){
vector<int> fac(n), ask(n);
if(mode){
forv(i,q) fac[i-1]=1;
forinc(i,1,n) if(fac[root(i)-1]) ask[i-1]=1;
} else{
forv(i,q) ask[i-1]=1;
}
return Query(ask);
}
int dnc(vector<int> l,int i){
if(l.back()==i) l.pop_back();
if(l.size()<2) return l[0];
vector<int> r;
while(l.size()>r.size()){
r.push_back(l.back());
l.pop_back();
}
l.push_back(i);
return tim(l) < l.size() ? dnc(l,i) : dnc(r,i);
}
int pf,sf;
void dnc1(vector<int> l,int i,int has=2){
if(l.size()<2){
if(pf) sf=l[0]; else pf=l[0];
return;
}
vector<int> r;
while(l.size()>r.size()){
r.push_back(l.back());
l.pop_back();
}
l.push_back(i);
int to=tim(l);
if(l.size()==to+1){
l.pop_back();
dnc1(l,i,1);
if(has>1) dnc1(r,i,1);
} else if(l.size()==to){
dnc1(r,i,has);
} else{
l.pop_back();
dnc1(l,i,has);
}
}
vector<int> ad[1111];
void add(int i,int j){
ad[i].push_back(j);
ad[j].push_back(i);
}
void Solve(int N){
n=N;
if(n==1){
Answer({1});
return;
}
vector<int> ask(n);
ask[0]=x[1]=y[1]=1;
vector<int> mp={1};
int tot=1;
forinc(i,2,n){
ask[i-1]=1;
int tmp=Query(ask);
if(tot<tmp){
mp.push_back(i);
x[i]=y[i]=i;
} else if(tot>tmp){
pf=sf=0;
if(i==4) mode=1;
dnc1(mp,i);
join(pf,i);
join(sf,i);
if(tim({x[pf],i},0)==1) add(x[pf],i), x[i]=y[pf]; else add(y[pf],i), y[i]=x[pf];
if(tim({x[sf],i},0)==1) add(x[sf],i), (x[i] ? y[i]=y[sf] : x[i]=y[sf]); else add(y[sf],i), (x[i] ? y[i]=x[sf] : x[i]=x[sf]);
fordec(i,mp.size()-1,0){
if(mp[i]==pf || mp[i]==sf){
swap(mp[i],mp.back());
mp.pop_back();
}
}
mp.push_back(i);
} else{
int to=dnc(mp,i);
join(i,to);
if(tim({x[to],i},0)==1){
add(i,x[to]);
x[to]=i;
} else{
add(i,y[to]);
y[to]=i;
}
}
tot=tmp;
}
int has=0;
forinc(i,1,n) has|=ad[i].size()==1;
if(!has) exit(-1);
forinc(i,1,n){
if(ad[i].size()==1){
vector<int> ans(n); ans[0]=i;
int pre=-1;
forinc(j,2,n){
forv(t,ad[i]){
if(t!=pre){
ans[j-1]=t;
pre=i;
i=t;
break;
}
}
}
Answer(ans);
return;
}
}
}
Compilation message
library.cpp: In function 'int dnc(std::vector<int>, int)':
library.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
return tim(l) < l.size() ? dnc(l,i) : dnc(r,i);
~~~~~~~^~~~~~~~~~
library.cpp: In function 'void dnc1(std::vector<int>, int, int)':
library.cpp:73:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(l.size()==to+1){
~~~~~~~~^~~~~~
library.cpp:77:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
} else if(l.size()==to){
~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
384 KB |
# of queries: 1203 |
| 2 |
Correct |
24 ms |
384 KB |
# of queries: 1198 |
| 3 |
Correct |
26 ms |
384 KB |
# of queries: 1273 |
| 4 |
Correct |
25 ms |
384 KB |
# of queries: 1263 |
| 5 |
Correct |
24 ms |
384 KB |
# of queries: 1269 |
| 6 |
Correct |
25 ms |
384 KB |
# of queries: 1258 |
| 7 |
Correct |
25 ms |
384 KB |
# of queries: 1252 |
| 8 |
Correct |
22 ms |
384 KB |
# of queries: 1188 |
| 9 |
Correct |
29 ms |
384 KB |
# of queries: 1270 |
| 10 |
Correct |
16 ms |
384 KB |
# of queries: 726 |
| 11 |
Correct |
4 ms |
384 KB |
# of queries: 0 |
| 12 |
Correct |
4 ms |
384 KB |
# of queries: 2 |
| 13 |
Correct |
4 ms |
384 KB |
# of queries: 4 |
| 14 |
Correct |
4 ms |
384 KB |
# of queries: 7 |
| 15 |
Correct |
5 ms |
384 KB |
# of queries: 46 |
| 16 |
Correct |
5 ms |
384 KB |
# of queries: 108 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
384 KB |
# of queries: 1203 |
| 2 |
Correct |
24 ms |
384 KB |
# of queries: 1198 |
| 3 |
Correct |
26 ms |
384 KB |
# of queries: 1273 |
| 4 |
Correct |
25 ms |
384 KB |
# of queries: 1263 |
| 5 |
Correct |
24 ms |
384 KB |
# of queries: 1269 |
| 6 |
Correct |
25 ms |
384 KB |
# of queries: 1258 |
| 7 |
Correct |
25 ms |
384 KB |
# of queries: 1252 |
| 8 |
Correct |
22 ms |
384 KB |
# of queries: 1188 |
| 9 |
Correct |
29 ms |
384 KB |
# of queries: 1270 |
| 10 |
Correct |
16 ms |
384 KB |
# of queries: 726 |
| 11 |
Correct |
4 ms |
384 KB |
# of queries: 0 |
| 12 |
Correct |
4 ms |
384 KB |
# of queries: 2 |
| 13 |
Correct |
4 ms |
384 KB |
# of queries: 4 |
| 14 |
Correct |
4 ms |
384 KB |
# of queries: 7 |
| 15 |
Correct |
5 ms |
384 KB |
# of queries: 46 |
| 16 |
Correct |
5 ms |
384 KB |
# of queries: 108 |
| 17 |
Correct |
251 ms |
452 KB |
# of queries: 8525 |
| 18 |
Correct |
246 ms |
384 KB |
# of queries: 8400 |
| 19 |
Correct |
231 ms |
544 KB |
# of queries: 8468 |
| 20 |
Correct |
227 ms |
504 KB |
# of queries: 7957 |
| 21 |
Correct |
211 ms |
384 KB |
# of queries: 7474 |
| 22 |
Correct |
252 ms |
504 KB |
# of queries: 8488 |
| 23 |
Correct |
242 ms |
384 KB |
# of queries: 8481 |
| 24 |
Correct |
90 ms |
384 KB |
# of queries: 3900 |
| 25 |
Correct |
221 ms |
552 KB |
# of queries: 8313 |
| 26 |
Correct |
220 ms |
504 KB |
# of queries: 7771 |
| 27 |
Correct |
84 ms |
424 KB |
# of queries: 3871 |
| 28 |
Correct |
40 ms |
428 KB |
# of queries: 1998 |
| 29 |
Correct |
46 ms |
456 KB |
# of queries: 1996 |
| 30 |
Correct |
50 ms |
424 KB |
# of queries: 1998 |
