This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |