QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#744565 | #9432. Permutation | sszcdjr | WA | 339ms | 3692kb | C++20 | 2.1kb | 2024-11-13 22:26:48 | 2024-11-13 22:26:51 |
Judging History
answer
#include <bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
vector<int> remp,remv;
int ans[1005],vis[1005],maxv,maxp,n,len;
int ask[1005];
int qry(int l1,int r1,int v1,int l2,int r2,int v2){
for(int i=1;i<=n;i++) ask[i]=maxp;
for(int i=1;i<=len;i++){
if(l1<=i&&i<=r1) ask[remp[i-1]]=v1;
else if(l2<=i&&i<=r2) ask[remp[i-1]]=v2;
else ask[remp[i-1]]=maxp;
}
cout<<"0 ";
for(int i=1;i<=n;i++) cout<<ask[i]<<" ";
cout<<endl; fflush(stdout);
int ret; cin>>ret;
return ret-1;
}
void solve1(int l,int r,int v){
if(l==r){
vis[v]=1;
ans[remp[l-1]]=v;
return ;
}
if(qry(l,mid,v,0,0,0)) solve1(l,mid,v);
else solve1(mid+1,r,v);
}
void solve2(int l1,int r1,int v1,int l2,int r2,int v2){
if(l1==r1&&l2==r2){
vis[v1]=1;
ans[remp[l1-1]]=v1;
vis[v2]=1;
ans[remp[l2-1]]=v2;
return ;
}
if(l1==r1){
vis[v1]=1;
ans[remp[l1-1]]=v1;
solve1(l2,r2,v2);
return ;
}
if(l2==r2){
vis[v2]=1;
ans[remp[l2-1]]=v2;
solve1(l1,r1,v1);
return ;
}
int ret=qry(l1,((l1+r1)>>1),v1,((l2+r2)>>1)+1,r2,v2);
if(ret==2){
solve2(l1,((l1+r1)>>1),v1,((l2+r2)>>1)+1,r2,v2);
}
else if(ret==0){
solve2(((l1+r1)>>1)+1,r1,v1,l2,((l2+r2)>>1),v2);
}
else{
ret=qry(l1,((l1+r1)>>1),v1,0,0,0);
if(ret) solve2(l1,((l1+r1)>>1),v1,l2,((l2+r2)>>1),v2);
else solve2(((l1+r1)>>1)+1,r1,v1,((l2+r2)>>1)+1,r2,v2);
}
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cout<<"0 "<<i<<" ";
for(int j=1;j<n;j++) cout<<1<<" "; cout<<endl; fflush(stdout);
int ret; cin>>ret;
if(ret>maxv) maxv=ret,maxp=i;
}
ans[1]=maxp; vis[maxp]=1;
for(int i=2;i<=n;i+=2){
remp.clear(),remv.clear();
for(int j=1;j<=n;j++) if(!ans[j]) remp.push_back(j);
for(int j=1;j<=n;j++) if(!vis[j]) remv.push_back(j);
// cout<<remp.size()<<" "<<remv.size()<<"\n";
random_shuffle(remp.begin(),remp.end());
random_shuffle(remv.begin(),remv.end());
if(i==n){
ans[remp[0]]=remv[0];
break;
}
else{
len=n-i+1;
solve2(1,n-i+1,remv[0],1,n-i+1,remv[1]);
}
}
cout<<1<<" "; for(int i=1;i<=n;i++) cout<<ans[i]<<" "; cout<<endl; fflush(stdout);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3632kb
input:
5 1 1 2 1 1 2 1 1 3
output:
0 1 1 1 1 1 0 2 1 1 1 1 0 3 1 1 1 1 0 4 1 1 1 1 0 5 1 1 1 1 0 3 1 2 2 1 0 3 1 3 3 1 0 3 3 1 2 3 0 3 4 3 3 5 1 3 4 2 1 5
result:
ok Accepted
Test #2:
score: -100
Wrong Answer
time: 339ms
memory: 3692kb
input:
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
wrong answer More than 6666 quries