QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#745337 | #9432. Permutation | Lazy_Labs | RE | 0ms | 0kb | C++14 | 1.5kb | 2024-11-14 09:15:35 | 2024-11-14 09:15:36 |
answer
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x(0),f(1);char c=getchar();
while(c<'0'||c>'9')f=c=='-'?-1:1,c=getchar();
while(c<='9'&&c>='0')x=x*10+c-48,c=getchar();
return x*f;
}
const int N=1010;
int p[N],n;vector<int>All;
int ask(int mid,int x,int y){
printf("0 ");
for(int i=1;i<=n;i++)printf("%d ",(i<=mid)?x:y);puts("");
fflush(stdout);return read();
}
queue<int>q;int fa[N],to[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void solve(int l,int r,vector<int>nw){
if(l==r)return p[l]=nw[0],void();
int mid=(l+r)>>1;for(auto i:nw)q.push(i),fa[i]=i,to[i]=-1;
int Pl=0,Pr=0;
while(!q.empty()){
if(q.size()==1){
int x=q.front();q.pop();
if(Pl)to[x]=!ask(mid,x,Pl);
else if(Pr)to[x]=!ask(mid,Pr,x);
}
else {
int x=q.front();q.pop();int y=q.front();q.pop();
int qry=ask(mid,x,y);
if(qry==0)to[x]=1,to[y]=0,Pl=y,Pr=x;
else if(qry==2)to[x]=0,to[y]=1,Pl=x,Pr=y;
else q.push(x),fa[find(y)]=find(x);
}
}
vector<int>L,R;
for(auto i:nw)if(!to[i])L.push_back(i);else R.push_back(i);
solve(l,mid,L);solve(mid+1,r,R);
}
mt19937 rnd(0xee0000);
int main(){
n=read();for(int i=1;i<=n;i++)All.push_back(i);shuffle(All.begin(),All.end(),rnd);
solve(1,n,All);printf("1 ");for(int i=1;i<=n;i++)printf("%d ",p[i]);fflush(stdout);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
5 1 1 1 0
output:
0 3 3 3 4 4 0 5 5 5 1 1 0 2 2 2 3 3 0 5 5 5 2 2