QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#740650#9432. Permutation-xcxxx-TL 0ms3684kbC++143.2kb2024-11-13 10:55:312024-11-13 10:55:40

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 10:55:40]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3684kb
  • [2024-11-13 10:55:31]
  • 提交

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) {
    rep(i,0,n-1) out[p[i+1]]=ask[i];
    printf("0 ");rep(i,1,n)printf("%d ",out[i]);
    puts(""),fflush(stdout);
    return rd();
}
#endif
#ifndef ONLINE_JUDGE
int a[N];
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) {
    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) {
    if(l==r) {
        ans[p[l]]=now[0];
        return;
    }
    int mid=(l+r)>>1;
    if(~out) {
        vector<int> L,R;
        for(int x:now) {
            vector<int> ask;
            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(out);
            rep(i,r+1,n) ask.push_back(x);
            if(query(ask)) L.push_back(x);
            else R.push_back(x);
        }
        solve(l, mid ,L,out);
        solve(mid+1,r,R,out);
    }
    else {
        vector<int> L,R,unknown;
        unknown.push_back(now.back());
        now.pop_back();
        for(int x:now) {
            vector<int> ask;
            if(!L.empty()) {
                rep(i,l,mid) ask.push_back(x);
                rep(i,mid+1,r) ask.push_back(L.front());
                if(query(ask)) L.push_back(x);
                else R.push_back(x);
            }
            else if(!R.empty()) {
                rep(i,l,mid) ask.push_back(R.front());
                rep(i,mid+1,r) ask.push_back(x);
                if(query(ask)) R.push_back(x);
                else L.push_back(x);
            }
            else {
                rep(i,l,mid) ask.push_back(x);
                rep(i,mid+1,r) ask.push_back(unknown.front());
                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);
            }
        }
        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() {
    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]);
    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: 0ms
memory: 3684kb

input:

5
1
0
0
1
1
1
0
1
0
1
0

output:

0 5 1 5 1 1 
0 5 2 5 2 2 
0 5 3 5 3 3 
0 5 4 5 4 4 
0 5 2 5 5 5 
0 1 2 1 1 1 
0 4 2 4 4 4 
0 5 5 5 2 5 
0 1 1 1 2 1 
0 5 2 2 2 2 
0 5 3 3 3 3 
1 3 4 2 1 5 

result:

ok Accepted

Test #2:

score: -100
Time Limit Exceeded

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: