#include <bits/stdc++.h>
#include "library.h"
using namespace std;
int n;
vector<int>otg;
struct cell
{
int st,l,r;
};
int islead[10005],p[40005],used[10005];
cell a[10005];
vector<int>v;
int get(int l,int r,int ad)
{
for(int i=l;i<=r;i++)
{
v[i-1]=1;
}
if(ad)v[ad-1]=1;
int q=Query(v);
for(int i=1;i<=n;i++)
{
v[i-1]=0;
}
return q;
}
void prec()
{
for(int i=1;i<=n;i++)
{
islead[i]=1;
a[i].st=i;
a[i].l=0;
a[i].r=0;
v.push_back(0);
}
}
void merg(int i,int j)
{
if(a[i].r==0)a[i].r=j;
else a[i].l=j;
if(a[j].r==0)a[j].r=i;
else a[j].l=i;
if(a[i].l!=0&&a[i].r!=0)islead[i]=0;
if(a[j].l!=0&&a[j].r!=0)islead[j]=0;
}
int bin(int l,int r,int i)
{
int L=l,R=r,m,h1,h2=0;
while(L<=R)
{
m=(L+R)/2;
h1=get(L,m,0);
if(n<=200)h2=get(L,m,i);
if(h1>=h2&&n<=200)R=m-1;
else L=m+1;
}
if(n<=200)return L;
else return l;
}
void fix(int l,int r,int h)
{
int mid=(l+r)/2,w,g;
for(int i=mid+1;i<=r;i++)
{
if(!islead[i])continue;
w=get(l,mid,i);
if(w==p[h*2]+1)continue;
g=bin(l,r,i);
//cout<<g<<" "<<i<<endl;
merg(g,i);
if(w==p[h*2])continue;
g=bin(g+1,mid,i);
//cout<<g<<" "<<i<<endl;
merg(g,i);
}
}
void build(int l,int r,int h)
{
if(l==r)
{
p[h]=1;
return;
}
int mid=(l+r)/2;
build(l,mid,h*2);
build(mid+1,r,h*2+1);
p[h]=get(l,r,0);
if(p[h]!=p[h*2]+p[h*2+1])
{
fix(l,r,h);
}
}
void Solve(int N)
{
n=N;
prec();
build(1,n,1);
int lead=1;
for(int i=1;i<=n;i++)
{
if(islead[i])
{
lead=i;
break;
}
}
if(n>200)
{
for(int i=1;i<=n;i++)otg.push_back(i);
Answer(otg);
return;
}
/*cout<<endl<<endl;
for(int i=1;i<=n;i++)
{
cout<<a[i].l<<" "<<a[i].r<<endl;
}
cout<<endl;*/
used[0]=1;
while(true)
{
used[lead]=1;
otg.push_back(lead);
if(!used[a[lead].l])lead=a[lead].l;
else if(!used[a[lead].r])lead=a[lead].r;
else break;
}
//for(int i=1;i<=n;i++)otg.push_back(i);
Answer(otg);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |