docker_space/frontier_cs_2/logs/gen_1.cpp

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

static char obuf[1<<22]; static int opos;
void oflush(){fwrite(obuf,1,opos,stdout);opos=0;fflush(stdout);}
void ochar(char c){obuf[opos++]=c;}
void oint(int x){
    if(x>=1000){ochar('0'+x/1000);ochar('0'+(x/100)%10);ochar('0'+(x/10)%10);ochar('0'+x%10);}
    else if(x>=100){ochar('0'+x/100);ochar('0'+(x/10)%10);ochar('0'+x%10);}
    else if(x>=10){ochar('0'+x/10);ochar('0'+x%10);}
    else ochar('0'+x);
}

int N,q[1001],perm[1001];
int kc; // known count (positions where perm[] is set and q[] matches)

int ask(){ochar('0');for(int i=0;i<N;i++){ochar(' ');oint(q[i]);}ochar('\n');oflush();int x;scanf("%d",&x);return x;}
void submit(){ochar('1');for(int i=0;i<N;i++){ochar(' ');oint(perm[i]);}ochar('\n');oflush();exit(0);}

// Divide and conquer: given a set of values and a set of positions,
// determine which value goes to which position.
// vals: values to place
// pos: positions (indices into the global position space)
// All non-pos positions in q[] are set to 1 (background, safe since pos1 is known)

void solve(vector<int>& vals, vector<int>& pos) {
    int n = vals.size();
    if (n == 0) return;
    if (n == 1) {
        // Single value, single position
        perm[pos[0]] = vals[0];
        q[pos[0]] = vals[0];
        kc++;
        return;
    }
    if (n == 2) {
        // 2 values, 2 positions. 1 query.
        q[pos[0]] = vals[0];
        int r = ask();
        q[pos[0]] = 1;
        if (r == kc + 1) {
            perm[pos[0]] = vals[0]; q[pos[0]] = vals[0];
            perm[pos[1]] = vals[1]; q[pos[1]] = vals[1];
        } else {
            perm[pos[0]] = vals[1]; q[pos[0]] = vals[1];
            perm[pos[1]] = vals[0]; q[pos[1]] = vals[0];
        }
        kc += 2;
        return;
    }

    // Split positions into left and right halves
    int half = n / 2;
    // left positions: pos[0..half-1], right positions: pos[half..n-1]

    // For each value, determine if it's in the left or right half.
    // Process values in pairs.
    vector<int> left_vals, right_vals;

    int vi = 0;
    while (vi < n) {
        if (vi + 1 >= n) {
            // Odd value out. Query to determine its half.
            int v = vals[vi];
            // Set left positions to v, rest to 1
            for (int i = 0; i < half; i++) q[pos[i]] = v;
            int r = ask();
            for (int i = 0; i < half; i++) q[pos[i]] = 1;
            if (r == kc + 1) left_vals.push_back(v);
            else right_vals.push_back(v);
            vi++;
            continue;
        }

        int v = vals[vi], w = vals[vi + 1];

        // Paired query: left=v, right=w
        for (int i = 0; i < half; i++) q[pos[i]] = v;
        for (int i = half; i < n; i++) q[pos[i]] = w;
        int r = ask();
        for (int i = 0; i < half; i++) q[pos[i]] = 1;
        for (int i = half; i < n; i++) q[pos[i]] = 1;

        if (r == kc + 2) {
            // v in left, w in right
            left_vals.push_back(v);
            right_vals.push_back(w);
        } else if (r == kc) {
            // v in right, w in left
            right_vals.push_back(v);
            left_vals.push_back(w);
        } else {
            // Same half. Disambiguate: query left=v only
            for (int i = 0; i < half; i++) q[pos[i]] = v;
            int r2 = ask();
            for (int i = 0; i < half; i++) q[pos[i]] = 1;
            if (r2 == kc + 1) {
                // Both in left
                left_vals.push_back(v);
                left_vals.push_back(w);
            } else {
                // Both in right
                right_vals.push_back(v);
                right_vals.push_back(w);
            }
        }
        vi += 2;
    }

    // Recurse on left and right
    vector<int> left_pos(pos.begin(), pos.begin() + half);
    vector<int> right_pos(pos.begin() + half, pos.end());
    solve(left_vals, left_pos);
    solve(right_vals, right_pos);
}

int main(){
    scanf("%d",&N);
    memset(perm,0,sizeof(perm));
    if(N==1){perm[0]=1;submit();}
    if(N==2){q[0]=1;q[1]=2;if(ask()==2){perm[0]=1;perm[1]=2;}else{perm[0]=2;perm[1]=1;}submit();}

    // Phase 1: Find pos1 and pos3 using bit queries
    int B=0;{int tmp=N-1;while(tmp>0){B++;tmp>>=1;}}
    int rb[12];
    for(int b=0;b<B;b++){
        for(int i=0;i<N;i++) q[i]=(i&(1<<b))?1:3;
        rb[b]=ask();
    }
    int kb1=0,kb3=0,kmask=0;
    for(int b=0;b<B;b++){
        if(rb[b]==0){kmask|=(1<<b);kb3|=(1<<b);}
        else if(rb[b]==2){kmask|=(1<<b);kb1|=(1<<b);}
    }
    int amask=((1<<B)-1)&~kmask,P=0;
    for(int b=0;b<B;b++){
        if(!(amask&(1<<b)))continue;
        for(int i=0;i<N;i++){
            q[i]=((i&(1<<b))&&(i&kmask)==kb1)?1:3;
        }
        int r=ask();
        if(r==2) P|=(1<<b);
    }
    int p1=kb1|(P&amask);
    int p3=kb3|(P&amask);
    if(p1<0||p1>=N||p3<0||p3>=N||p1==p3){
        p1=-1;p3=-1;
        for(int i=0;i<N;i++){
            if(p1>=0&&p3>=0)break;
            for(int j=0;j<N;j++)q[j]=3;q[i]=1;
            int r=ask();
            if(r==2)p1=i;else if(r==0)p3=i;
        }
    }

    perm[p1]=1;perm[p3]=3;
    kc=2;
    for(int i=0;i<N;i++) q[i]=1;
    q[p1]=1;q[p3]=3;

    // Collect unknown values and positions
    vector<int> vals, pos;
    vals.push_back(2);
    for(int v=4;v<=N;v++) vals.push_back(v);
    for(int i=0;i<N;i++) if(i!=p1&&i!=p3) pos.push_back(i);

    // Divide and conquer
    solve(vals, pos);

    submit();
}