QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#740730 | #9432. Permutation | -xcxxx- | WA | 360ms | 3816kb | C++14 | 3.5kb | 2024-11-13 11:18:15 | 2024-11-13 11:18:16 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
using namespace std;
int rd() {int x=0,f=1;char c=getchar();while(!isdigit(c))f=(c=='-'?-1:f),c=getchar();while(isdigit(c))x=x*10+c-'0',c=getchar();return x*f;}
const int N=1005;
int n,p[N],ans[N];
int out[N];
#ifdef ONLINE_JUDGE
void init() {
}
int query(vector<int> ask) {
assert(ask.size()==n);
rep(i,0,n-1) out[p[i+1]]=ask[i];
printf("0 ");rep(i,1,n)printf("%d ",out[i]);
puts(""),fflush(stdout);
int res;cin>>res;
return res;
}
#endif
#ifndef ONLINE_JUDGE
int a[N],qcnt;
void init() {
rep(i,1,n) a[i]=i;
random_shuffle(a+1,a+1+n);
printf("ANS: ");rep(i,1,n) printf("%d ",a[i]);puts("");
}
int query(vector<int> ask) {
qcnt++;
rep(i,0,n-1) out[p[i+1]]=ask[i];
printf("0 ");rep(i,1,n)printf("%d ",out[i]);
puts(""),fflush(stdout);
int cnt=0;
rep(i,1,n) cnt+=out[i]==a[i];
printf("%d\n",cnt);
return cnt;
}
#endif
void solve(int l,int r,vector<int> now,int out=-1) {
fprintf(stderr,"l=%d r=%d\n",l,r);
if(l==r) {
ans[p[l]]=now[0];
return;
}
int mid=(l+r)>>1;
vector<int> L,R,unknown;
unknown.push_back(now.back());
now.pop_back();
for(int x:now) {
assert(x<=1000);
if(L.size()==mid-l+1) {R.push_back(x);continue;}
if(R.size()==r-mid) {L.push_back(x);continue;}
vector<int> ask;
if(!unknown.empty()) {
rep(i,1,l-1) ask.push_back(x);
rep(i,l,mid) ask.push_back(x);
rep(i,mid+1,r) ask.push_back(unknown.front());
rep(i,r+1,n) ask.push_back(x);
int val=query(ask);
if(val==0) {
R.push_back(x);
for(int y:unknown) L.push_back(y);
unknown.clear();
}
if(val==2) {
L.push_back(x);
for(int y:unknown) R.push_back(y);
unknown.clear();
}
if(val==1) unknown.push_back(x);
}
else if(!L.empty()) {
rep(i,1,l-1) ask.push_back(x);
rep(i,l,mid) ask.push_back(x);
rep(i,mid+1,r) ask.push_back(L.front());
rep(i,r+1,n) ask.push_back(x);
if(query(ask)) L.push_back(x);
else R.push_back(x);
}
else if(!R.empty()) {
rep(i,1,l-1) ask.push_back(x);
rep(i,l,mid) ask.push_back(R.front());
rep(i,mid+1,r) ask.push_back(x);
rep(i,r+1,n) ask.push_back(x);
if(query(ask)) R.push_back(x);
else L.push_back(x);
}
// printf("L: ");for(int x:L) printf("%d ",x);puts("");
// printf("R: ");for(int x:R) printf("%d ",x);puts("");
// printf("unknown: ");for(int x:unknown) printf("%d ",x);puts("");
}
if(L.size()<mid-l+1) for(int x:unknown) L.push_back(x);
if(R.size()<r-mid) for(int x:unknown) R.push_back(x);
solve(l, mid ,L,R.front());
solve(mid+1,r,R,L.front());
}
signed main() {
// freopen("K.out","w",stdout);
n=rd();
init();
rep(i,1,n) p[i]=i;
random_shuffle(p+1,p+1+n);
vector<int> now;
rep(i,1,n) now.push_back(i);
solve(1,n,now);
printf("1 ");
rep(i,1,n) printf("%d ",ans[i]);
puts("");
// fprintf(stderr,"%d queries\n",qcnt);
return 0;
}
//g++ -fsanitize=address,undefined -Wall -std=c++14 -O2 -o K K.cpp
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3744kb
input:
5 1 0 0 2 2 2
output:
0 5 1 5 1 1 0 5 2 5 2 2 0 5 3 5 3 3 0 5 4 5 5 5 0 5 5 5 1 5 0 3 2 2 2 2 1 3 4 2 1 5
result:
ok Accepted
Test #2:
score: -100
Wrong Answer
time: 360ms
memory: 3816kb
input:
1000 1 1 2 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 0 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 1...
output:
0 1000 1000 1 1000 1000 1000 1000 1000 1000 1 1000 1000 1 1 1000 1 1 1000 1 1 1 1000 1 1000 1000 1 1 1000 1000 1 1000 1000 1000 1 1000 1 1000 1000 1 1000 1 1000 1 1 1 1 1 1 1 1 1 1 1000 1000 1000 1 1 1 1 1 1 1 1000 1000 1 1000 1 1 1 1 1 1 1 1000 1 1000 1 1000 1 1000 1 1000 1 1 1000 1 1 1000 1000 1 1...
result:
wrong answer More than 6666 quries