#include "library.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define vi vector<int>
#define vl vector<ll>
#define all(a) begin(a),end(a)
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
int n,col[1010],par[1010];
vi sa[1010];
vi ch[1010];
map<pii,int> ma;
vi sol;
void merge(int a,int b)
{
ch[a].pb(b);
ch[b].pb(a);
bool cha=col[a]==col[b];
a=par[a];
b=par[b];
for (auto x: sa[b])
{
sa[a].pb(x);
par[x]=a;
if (cha) col[x]^=1;
}
}
void dfs(int i,int p=-1)
{
sol.pb(i+1);
for (auto a: ch[i]) if (a!=p) dfs(a,i);
}
int f(int l,int r)
{
if (r<=l) return r-l+1;
if (ma.find({l,r})!=ma.end()) return ma[{l,r}];
vi v;
for (int j=0;j<l;++j) v.pb(0);
for (int j=l;j<=r;++j) v.pb(1);
for (int j=r+1;j<n;++j) v.pb(0);
return ma[{l,r}]=Query(v);
}
void Solve(int N)
{
n=N;
for (int i=0;i<n;++i) par[i]=i,col[i]=0,sa[i]={i};
int la=0;
while (la<n-1)
{
int c=f(0,la)-la;
while (f(0,la)-la==c) ++la;
int dif=c-(f(0,la)-la);
int lo=-1,hi=la-1;
while (lo<hi)
{
int mid=(lo+hi+1)/2;
vi v(n);
int cn=0;
for (int i=mid;i<la;++i) if (col[i]==0) v[i]=1,++cn;
v[la]=1,++cn;
if (Query(v)==cn)
{
cn=0;
v=vi(n,0);
for (int i=mid;i<la;++i) if (col[i]==1) v[i]=1,++cn;
v[la]=1,++cn;
if (Query(v)==cn) hi=mid-1;
else lo=mid;
}
else lo=mid;
}
merge(la,lo);
if (dif==2)
{
int pre=lo;
lo=-1,hi=la-1;
while (lo<hi)
{
int mid=(lo+hi+1)/2;
vi v(n);
int cn=0;
for (int i=mid;i<la;++i) if (col[i]==0 && i!=pre) v[i]=1,++cn;
v[la]=1,++cn;
if (Query(v)==cn)
{
cn=0;
v=vi(n,0);
for (int i=mid;i<la;++i) if (col[i]==1 && i!=pre) v[i]=1,++cn;
v[la]=1,++cn;
if (Query(v)==cn) hi=mid-1;
else lo=mid;
}
else lo=mid;
}
merge(la,lo);
}
}
for (int i=0;i<n;++i) if (ch[i].size()<=1)
{
dfs(i);
break;
}
Answer(sol);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
384 KB |
# of queries: 2377 |
| 2 |
Correct |
41 ms |
384 KB |
# of queries: 2370 |
| 3 |
Correct |
43 ms |
384 KB |
# of queries: 2460 |
| 4 |
Correct |
42 ms |
444 KB |
# of queries: 2437 |
| 5 |
Correct |
46 ms |
384 KB |
# of queries: 2481 |
| 6 |
Correct |
48 ms |
384 KB |
# of queries: 2480 |
| 7 |
Correct |
43 ms |
384 KB |
# of queries: 2427 |
| 8 |
Correct |
44 ms |
512 KB |
# of queries: 2316 |
| 9 |
Correct |
44 ms |
384 KB |
# of queries: 2468 |
| 10 |
Correct |
27 ms |
384 KB |
# of queries: 1433 |
| 11 |
Correct |
4 ms |
384 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
384 KB |
# of queries: 2 |
| 13 |
Correct |
5 ms |
384 KB |
# of queries: 7 |
| 14 |
Correct |
5 ms |
416 KB |
# of queries: 12 |
| 15 |
Correct |
5 ms |
428 KB |
# of queries: 86 |
| 16 |
Correct |
7 ms |
384 KB |
# of queries: 204 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
384 KB |
# of queries: 2377 |
| 2 |
Correct |
41 ms |
384 KB |
# of queries: 2370 |
| 3 |
Correct |
43 ms |
384 KB |
# of queries: 2460 |
| 4 |
Correct |
42 ms |
444 KB |
# of queries: 2437 |
| 5 |
Correct |
46 ms |
384 KB |
# of queries: 2481 |
| 6 |
Correct |
48 ms |
384 KB |
# of queries: 2480 |
| 7 |
Correct |
43 ms |
384 KB |
# of queries: 2427 |
| 8 |
Correct |
44 ms |
512 KB |
# of queries: 2316 |
| 9 |
Correct |
44 ms |
384 KB |
# of queries: 2468 |
| 10 |
Correct |
27 ms |
384 KB |
# of queries: 1433 |
| 11 |
Correct |
4 ms |
384 KB |
# of queries: 0 |
| 12 |
Correct |
5 ms |
384 KB |
# of queries: 2 |
| 13 |
Correct |
5 ms |
384 KB |
# of queries: 7 |
| 14 |
Correct |
5 ms |
416 KB |
# of queries: 12 |
| 15 |
Correct |
5 ms |
428 KB |
# of queries: 86 |
| 16 |
Correct |
7 ms |
384 KB |
# of queries: 204 |
| 17 |
Correct |
448 ms |
760 KB |
# of queries: 16180 |
| 18 |
Correct |
436 ms |
888 KB |
# of queries: 15999 |
| 19 |
Correct |
441 ms |
760 KB |
# of queries: 16173 |
| 20 |
Correct |
397 ms |
640 KB |
# of queries: 15115 |
| 21 |
Correct |
375 ms |
612 KB |
# of queries: 14160 |
| 22 |
Correct |
439 ms |
672 KB |
# of queries: 16070 |
| 23 |
Correct |
442 ms |
604 KB |
# of queries: 16080 |
| 24 |
Correct |
153 ms |
524 KB |
# of queries: 7445 |
| 25 |
Correct |
435 ms |
652 KB |
# of queries: 15726 |
| 26 |
Correct |
395 ms |
632 KB |
# of queries: 14774 |
| 27 |
Correct |
165 ms |
632 KB |
# of queries: 7488 |
| 28 |
Correct |
279 ms |
3192 KB |
# of queries: 9976 |
| 29 |
Correct |
279 ms |
3200 KB |
# of queries: 9965 |
| 30 |
Correct |
282 ms |
3192 KB |
# of queries: 9976 |
