QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#744660 | #9432. Permutation | sszcdjr | RE | 318ms | 3868kb | C++20 | 2.5kb | 2024-11-13 22:44:42 | 2024-11-13 22:44:43 |
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;
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]);
}
if(cnt>6600){
if(i>=500) exit(2);
else exit(0);
}
}
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: 3716kb
input:
5 1 2 1 1 1
output:
0 2 1 1 1 1 0 3 1 1 1 1 0 3 2 5 5 2 0 3 5 3 2 3 0 3 1 3 4 3 1 3 4 2 1 5
result:
ok Accepted
Test #2:
score: 0
Accepted
time: 318ms
memory: 3780kb
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 2 2 2 2 2 3 3 1 1 2 2 2 2 1 3 3 2 1 2 1 1 3 3 2 2 1 1 2 2 1 2 1 2 1 3 2 1 2 2 2 2 3 3 2 1 2 1 2 2 2 1 2 1 2 1 2 2 2 1 2 1 2 2 1 3 3 2 1 1 1...
output:
0 543 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:
ok Accepted
Test #3:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
1 1
output:
0 1 1 1
result:
ok Accepted
Test #4:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
2 2 1
output:
0 2 1 0 1 1 1 2 1
result:
ok Accepted
Test #5:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
3 2 1 3
output:
0 3 1 1 0 1 1 1 0 3 1 2 1 3 1 2
result:
ok Accepted
Test #6:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
4 1 2 1 2
output:
0 2 1 1 1 0 3 1 1 1 0 3 1 4 4 0 3 3 3 1 1 3 4 2 1
result:
ok Accepted
Test #7:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
6 1 2 3 2 2 2 1 1
output:
0 6 1 1 1 1 1 0 3 1 1 1 1 1 0 3 5 5 6 6 5 0 3 5 3 6 3 5 0 3 5 3 3 3 5 0 3 3 3 3 3 5 0 3 2 1 2 3 3 0 3 1 3 3 3 3 1 3 4 2 1 6 5
result:
ok Accepted
Test #8:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
7 2 1 2 2 2 2 3 2 2 1 3
output:
0 3 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 3 5 2 2 5 2 5 0 3 3 2 2 3 2 3 0 3 3 2 5 3 2 3 0 3 3 2 3 3 2 3 0 3 3 2 3 3 5 3 0 3 1 3 4 1 3 4 0 3 3 3 4 3 3 4 0 3 3 3 4 3 3 1 0 3 7 3 3 6 3 3 1 3 7 2 1 6 5 4
result:
ok Accepted
Test #9:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
8 1 2 1 2 1 1 3 1 1 2
output:
0 7 1 1 1 1 1 1 1 0 3 1 1 1 1 1 1 1 0 3 8 1 8 8 1 1 1 0 3 1 8 3 1 3 3 8 0 3 1 3 3 1 3 3 3 0 3 3 8 3 3 3 3 3 0 3 4 2 3 2 2 4 3 0 3 4 3 3 2 2 3 3 0 3 6 3 3 5 6 3 3 0 3 3 3 3 3 5 3 3 1 3 7 2 1 6 5 4 8
result:
ok Accepted
Test #10:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
9 1 1 1 1 1 1 1 2 2 1 3 3 2 1 2 2 3 1 3 1
output:
0 8 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 9 1 1 1 1 1 1 1 1 0 6 1 1 1 1 1 1 1 1 0 4 1 1 1 1 1 1 1 1 0 7 1 1 1 1 1 1 1 1 0 2 1 1 1 1 1 1 1 1 0 3 1 1 1 1 1 1 1 1 0 3 9 8 9 8 9 9 8 8 0 3 9 3 9 3 9 9 3 3 0 3 3 8 3 9 3 3 8 9 0 3 3 3 3 9 3 3 8 3 0 3 7 5 5 3 7 7 3 5 0 3 3 5 5 3 3 3 3 5 0 3 5 ...
result:
ok Accepted
Test #11:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
10 1 2 2 1 3 2 2 1 2 1 1 1 3 3 2
output:
0 10 1 1 1 1 1 1 1 1 1 0 3 1 1 1 1 1 1 1 1 1 0 3 10 10 7 7 7 7 10 7 10 0 3 3 3 7 7 7 7 3 7 3 0 3 7 10 3 3 3 3 7 3 10 0 3 7 3 3 3 3 3 3 3 10 0 3 7 3 3 3 3 3 3 3 3 0 3 3 3 5 6 6 5 6 5 6 0 3 3 3 6 3 5 6 3 3 5 0 3 3 3 6 3 3 6 3 3 3 0 3 3 3 3 3 3 3 3 3 5 0 3 3 3 4 4 3 1 1 3 1 0 3 3 3 1 3 3 4 ...
result:
ok Accepted
Test #12:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
11 1 1 1 1 1 1 1 1 1 2 3 2 2 2 1 2 2 1 2 2 1 3 1 1 2 1 3
output:
0 8 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 9 1 1 1 1 1 1 1 1 1 1 0 6 1 1 1 1 1 1 1 1 1 1 0 4 1 1 1 1 1 1 1 1 1 1 0 7 1 1 1 1 1 1 1 1 1 1 0 2 1 1 1 1 1 1 1 1 1 1 0 10 1 1 1 1 1 1 1 1 1 1 0 11 1 1 1 1 1 1 1 1 1 1 0 3 1 1 1 1 1 1 1 1 1 1 0 3 11 10 11 11 10 10 11 10 10 11 0 3 11 10 3 3...
result:
ok Accepted
Test #13:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
12 1 2 2 2 1 1 2 2 1 1 2 2 3 3 1 1 1 1 1 1
output:
0 10 1 1 1 1 1 1 1 1 1 1 1 0 3 1 1 1 1 1 1 1 1 1 1 1 0 3 10 10 10 10 1 10 1 10 1 1 1 0 3 10 10 10 10 3 10 3 10 3 3 3 0 3 1 1 10 1 3 10 3 10 3 3 3 0 3 10 3 3 10 3 1 3 3 3 3 3 0 3 3 3 1 3 3 3 3 3 3 3 3 0 3 5 3 3 5 2 5 5 5 2 2 2 0 3 5 3 3 5 3 5 5 5 3 3 3 0 3 3 3 3 3 2 3 3 3 5 2 5 0 3 3 3 3 3 ...
result:
ok Accepted
Test #14:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
13 1 1 2 3 2 2 3 1 2 1 3 3 2 3 2 1 2 2 2 1 1 1 2 2 3 1
output:
0 8 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 13 1 1 1 1 1 1 1 1 1 1 1 1 0 13 3 6 6 3 6 6 3 6 3 3 6 3 0 13 13 6 13 3 13 6 3 13 13 3 6 13 0 13 13 6 13 13 13 6 13 13 13 13 6 13 0 13 13 6 13 13 13 13 13 13 13 13 6 3 0 13 13 6 13 13 13 13 13 13 13 13 13 13 0 13 12 8 8 12 8 8 8 12 12 ...
result:
ok Accepted
Test #15:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
14 2 1 2 1 1 3 2 3 1 1 2 2 2 2 1 3 2 2 1 3 2 2 2 2 3 1 1
output:
0 13 1 1 1 1 1 1 1 1 1 1 1 1 1 0 3 1 1 1 1 1 1 1 1 1 1 1 1 1 0 13 5 5 5 2 5 2 2 5 2 5 5 2 2 0 13 5 5 5 13 5 13 13 5 13 5 5 13 13 0 13 13 13 13 2 13 5 5 13 5 13 13 2 2 0 13 13 13 13 5 13 13 13 13 2 13 13 13 5 0 13 13 13 13 13 13 13 13 13 13 13 13 13 5 0 13 3 9 3 9 3 9 3 9 13 9 3 3 13 0 13 13 ...
result:
ok Accepted
Test #16:
score: 0
Accepted
time: 1ms
memory: 3724kb
input:
15 1 1 2 3 2 2 2 2 3 2 2 3 1 2 1 3 3 2 2 1 1 2 2 1 3 1 3 2 2 1
output:
0 15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 14 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 13 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 13 4 15 15 4 15 4 4 4 4 4 15 15 15 15 0 13 13 15 15 13 13 4 13 4 4 4 13 13 13 15 0 13 13 13 13 13 13 4 13 4 4 4 13 13 13 13 0 13 13 13 13 13 13 4 13 13 4 13 15 15 13 13 0 13 13 13 13 13 13 4 1...
result:
ok Accepted
Test #17:
score: -100
Runtime Error
input:
975 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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 791 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...