#include<bits/stdc++.h>
#include "library.h"
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define inf 1010000000
//#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {static int cnt=0;cerr << x << endl;cnt++;if(cnt>1000) exit(0);}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif
const int maxn=1005;
vector<int> adj[maxn],res;
void dfs(int u, int par){
res.pb(u+1);
for(auto v: adj[u]) if(v!=par) dfs(v,u);
}
void Solve(int n){
if(n==1){
Answer({1});
return;
}
vector<int> tmp;
int val[maxn],l,r,mid,x;
val[0]=1;
rep2(i,1,n){
tmp.clear();
rep1(j,i+1) tmp.pb(1);
rep2(j,i+1,n) tmp.pb(0);
val[i]=Query(tmp);
if(val[i]==val[i-1]+1) continue;
if(val[i]==val[i-1]){
l=0,r=i-1;
while(l<r){
mid=l+r>>1;
tmp=vector<int>(n,0);
rep1(j,mid+1) tmp[j]=1;
tmp[i]=1;
if(Query(tmp)==val[mid]) r=mid;
else l=mid+1;
}
adj[l].pb(i),adj[i].pb(l);
continue;
}
l=0,r=i-1;
while(l<r){
mid=l+r>>1;
tmp=vector<int>(n,0);
rep1(j,mid+1) tmp[j]=1;
tmp[i]=1;
if(Query(tmp)<=val[mid]) r=mid;
else l=mid+1;
}
x=l;
adj[x].pb(i),adj[i].pb(x);
l=x+1,r=i-1;
while(l<r){
mid=l+r>>1;
tmp=vector<int>(n,0);
rep1(j,mid+1) tmp[j]=1;
tmp[i]=1;
if(Query(tmp)<val[mid]) r=mid;
else l=mid+1;
}
adj[l].pb(i),adj[i].pb(l);
}
rep(n) if(sz(adj[i])==1){
dfs(i,-1);
Answer(res);
break;
}
}
Compilation message
library.cpp: In function 'void Solve(int)':
library.cpp:54:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | mid=l+r>>1;
| ~^~
library.cpp:66:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | mid=l+r>>1;
| ~^~
library.cpp:77:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
77 | mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
492 KB |
# of queries: 1464 |
| 2 |
Correct |
28 ms |
364 KB |
# of queries: 1471 |
| 3 |
Correct |
19 ms |
492 KB |
# of queries: 1534 |
| 4 |
Correct |
29 ms |
364 KB |
# of queries: 1542 |
| 5 |
Correct |
28 ms |
364 KB |
# of queries: 1529 |
| 6 |
Correct |
30 ms |
364 KB |
# of queries: 1533 |
| 7 |
Correct |
20 ms |
364 KB |
# of queries: 1542 |
| 8 |
Correct |
22 ms |
620 KB |
# of queries: 1457 |
| 9 |
Correct |
17 ms |
404 KB |
# of queries: 1547 |
| 10 |
Correct |
16 ms |
364 KB |
# of queries: 903 |
| 11 |
Correct |
1 ms |
364 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
364 KB |
# of queries: 1 |
| 13 |
Correct |
1 ms |
364 KB |
# of queries: 3 |
| 14 |
Correct |
1 ms |
364 KB |
# of queries: 6 |
| 15 |
Correct |
1 ms |
364 KB |
# of queries: 53 |
| 16 |
Correct |
2 ms |
364 KB |
# of queries: 124 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
492 KB |
# of queries: 1464 |
| 2 |
Correct |
28 ms |
364 KB |
# of queries: 1471 |
| 3 |
Correct |
19 ms |
492 KB |
# of queries: 1534 |
| 4 |
Correct |
29 ms |
364 KB |
# of queries: 1542 |
| 5 |
Correct |
28 ms |
364 KB |
# of queries: 1529 |
| 6 |
Correct |
30 ms |
364 KB |
# of queries: 1533 |
| 7 |
Correct |
20 ms |
364 KB |
# of queries: 1542 |
| 8 |
Correct |
22 ms |
620 KB |
# of queries: 1457 |
| 9 |
Correct |
17 ms |
404 KB |
# of queries: 1547 |
| 10 |
Correct |
16 ms |
364 KB |
# of queries: 903 |
| 11 |
Correct |
1 ms |
364 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
364 KB |
# of queries: 1 |
| 13 |
Correct |
1 ms |
364 KB |
# of queries: 3 |
| 14 |
Correct |
1 ms |
364 KB |
# of queries: 6 |
| 15 |
Correct |
1 ms |
364 KB |
# of queries: 53 |
| 16 |
Correct |
2 ms |
364 KB |
# of queries: 124 |
| 17 |
Correct |
169 ms |
408 KB |
# of queries: 10051 |
| 18 |
Correct |
203 ms |
492 KB |
# of queries: 9919 |
| 19 |
Correct |
225 ms |
492 KB |
# of queries: 10022 |
| 20 |
Correct |
178 ms |
624 KB |
# of queries: 9386 |
| 21 |
Correct |
152 ms |
492 KB |
# of queries: 8822 |
| 22 |
Correct |
195 ms |
492 KB |
# of queries: 10074 |
| 23 |
Correct |
224 ms |
492 KB |
# of queries: 10033 |
| 24 |
Correct |
75 ms |
408 KB |
# of queries: 4661 |
| 25 |
Correct |
220 ms |
620 KB |
# of queries: 9825 |
| 26 |
Correct |
182 ms |
508 KB |
# of queries: 9186 |
| 27 |
Correct |
89 ms |
364 KB |
# of queries: 4646 |
| 28 |
Correct |
209 ms |
880 KB |
# of queries: 8977 |
| 29 |
Correct |
174 ms |
492 KB |
# of queries: 8967 |
| 30 |
Correct |
144 ms |
492 KB |
# of queries: 8977 |
