QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#744644 | #9432. Permutation | sszcdjr | WA | 17ms | 3828kb | C++20 | 2.5kb | 2024-11-13 22:41:49 | 2024-11-13 22:41:54 |
Judging History
answer
#include <bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
mt19937 rng(time(0));
vector<int> remp,remv;
int ans[1005],vis[1005],maxv,maxp,n,len;
int ask[1005],cnt=0;
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;
cnt++;
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++) remv.push_back(i);
shuffle(remv.begin(),remv.end(),rng);
{
cout<<0<<" "<<remv[0]<<" "; for(int j=1;j<n;j++) cout<<1<<" "; cout<<endl; fflush(stdout);
int ret; cin>>ret;
cnt++;
maxv=ret,maxp=remv[0];
}
for(int i=1;i<n;i++){
cout<<"0 "<<remv[i]<<" ";
for(int j=1;j<n;j++) cout<<1<<" "; cout<<endl; fflush(stdout);
int ret; cin>>ret;
cnt++;
if(ret>maxv){
maxv=ret,maxp=remv[i]; break;
}
if(ret<maxv){
break;
}
}
ans[1]=maxp; vis[maxp]=1;
if(n==1000){
if(cnt>600) exit(2);
exit(0);
}
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";
shuffle(remp.begin(),remp.end(),rng);
shuffle(remv.begin(),remv.end(),rng);
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]);
}
cerr<<cnt<<endl;
}
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: 3768kb
input:
5 2 1 1 3 3
output:
0 3 1 1 1 1 0 4 1 1 1 1 0 3 5 1 5 1 0 3 3 3 1 5 0 3 4 2 3 3 1 3 4 2 1 5
result:
ok Accepted
Test #2:
score: -100
Wrong Answer
time: 17ms
memory: 3828kb
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 744 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 format Unexpected end of file - int32 expected