docker_space/frontier_cs_2/logs/gen_3.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;

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);}

int par[1001];
int Find(int x){return par[x]==x?x:par[x]=Find(par[x]);}
void Unite(int a,int b){par[Find(a)]=Find(b);}

void solve(vector<int>& vals, vector<int>& pos) {
    int n = vals.size();
    if (n == 0) return;
    if (n == 1) {
        perm[pos[0]] = vals[0]; q[pos[0]] = vals[0]; kc++;
        return;
    }
    if (n == 2) {
        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;
    }
    if (n == 3) {
        // Special case: 3 values, 3 positions.
        // Query 1: assign v0,v1,v2 to pos[0],pos[1],pos[2]
        q[pos[0]] = vals[0]; q[pos[1]] = vals[1]; q[pos[2]] = vals[2];
        int r1 = ask();
        q[pos[0]] = 1; q[pos[1]] = 1; q[pos[2]] = 1;

        if (r1 == kc + 3) {
            perm[pos[0]]=vals[0]; q[pos[0]]=vals[0];
            perm[pos[1]]=vals[1]; q[pos[1]]=vals[1];
            perm[pos[2]]=vals[2]; q[pos[2]]=vals[2];
            kc += 3; return;
        }

        // Query 2: assign v0,v2,v1
        q[pos[0]] = vals[0]; q[pos[1]] = vals[2]; q[pos[2]] = vals[1];
        int r2 = ask();
        q[pos[0]] = 1; q[pos[1]] = 1; q[pos[2]] = 1;

        if (r2 == kc + 3) {
            perm[pos[0]]=vals[0]; q[pos[0]]=vals[0];
            perm[pos[1]]=vals[2]; q[pos[1]]=vals[2];
            perm[pos[2]]=vals[1]; q[pos[2]]=vals[1];
            kc += 3; return;
        }

        // From the analysis:
        // (v0,v1,v2): r1=3, r2=1 -> handled above
        // (v0,v2,v1): r1=1, r2=3 -> handled above
        // (v1,v0,v2): r1=1, r2=0
        // (v1,v2,v0): r1=0, r2=1
        // (v2,v0,v1): r1=0, r2=1
        // (v2,v1,v0): r1=1, r2=0

        // Adjusted for kc offset:
        int s1 = r1 - kc, s2 = r2 - kc;

        if (s1 == 1 && s2 == 0) {
            // (v1,v0,v2) or (v2,v1,v0)
            // Query 3: test if pos[0] has v1
            q[pos[0]] = vals[1];
            int r3 = ask();
            q[pos[0]] = 1;
            if (r3 == kc + 1) {
                // pos[0]=v1
                perm[pos[0]]=vals[1]; q[pos[0]]=vals[1];
                perm[pos[1]]=vals[0]; q[pos[1]]=vals[0];
                perm[pos[2]]=vals[2]; q[pos[2]]=vals[2];
            } else {
                perm[pos[0]]=vals[2]; q[pos[0]]=vals[2];
                perm[pos[1]]=vals[1]; q[pos[1]]=vals[1];
                perm[pos[2]]=vals[0]; q[pos[2]]=vals[0];
            }
            kc += 3; return;
        }

        if (s1 == 0 && s2 == 1) {
            // (v1,v2,v0) or (v2,v0,v1)
            q[pos[0]] = vals[1];
            int r3 = ask();
            q[pos[0]] = 1;
            if (r3 == kc + 1) {
                perm[pos[0]]=vals[1]; q[pos[0]]=vals[1];
                perm[pos[1]]=vals[2]; q[pos[1]]=vals[2];
                perm[pos[2]]=vals[0]; q[pos[2]]=vals[0];
            } else {
                perm[pos[0]]=vals[2]; q[pos[0]]=vals[2];
                perm[pos[1]]=vals[0]; q[pos[1]]=vals[0];
                perm[pos[2]]=vals[1]; q[pos[2]]=vals[1];
            }
            kc += 3; return;
        }

        // Shouldn't reach here
        // Fallback
        perm[pos[0]]=vals[0]; q[pos[0]]=vals[0];
        perm[pos[1]]=vals[1]; q[pos[1]]=vals[1];
        perm[pos[2]]=vals[2]; q[pos[2]]=vals[2];
        kc += 3;
        return;
    }

    int half = n / 2;

    // Initialize Union-Find
    for (int i = 0; i < n; i++) par[i] = i;

    vector<int> half_known(n, -1);
    vector<int> same_half_reps;

    // Phase 1: pair values
    for (int vi = 0; vi + 1 < n; vi += 2) {
        int v = vals[vi], w = vals[vi + 1];
        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) {
            half_known[vi] = 0; half_known[vi + 1] = 1;
        } else if (r == kc) {
            half_known[vi] = 1; half_known[vi + 1] = 0;
        } else {
            Unite(vi, vi + 1);
            same_half_reps.push_back(Find(vi));
        }
    }

    // Handle odd value: instead of standalone query, pair it with first same-half group
    if (n % 2 == 1) {
        int vi = n - 1;
        if (!same_half_reps.empty()) {
            // Pair odd value with a same-half representative
            int rep = same_half_reps.back();
            same_half_reps.pop_back();
            int v = vals[vi]; // odd value
            // Find a value from the same-half group
            int w = -1;
            for (int i = 0; i < n; i++) {
                if (Find(i) == Find(rep)) { w = vals[i]; break; }
            }
            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 (odd) in left, w (rep group) in right
                half_known[vi] = 0;
                for (int i = 0; i < n; i++) {
                    if (Find(i) == Find(rep)) half_known[i] = 1;
                }
            } else if (r == kc) {
                half_known[vi] = 1;
                for (int i = 0; i < n; i++) {
                    if (Find(i) == Find(rep)) half_known[i] = 0;
                }
            } else {
                // Same half: odd value and entire group are in same half
                Unite(vi, rep);
                same_half_reps.push_back(Find(vi));
            }
        } else {
            // No same-half groups, query alone
            int v = vals[vi];
            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;
            half_known[vi] = (r == kc + 1) ? 0 : 1;
        }
    }

    // Phase 2: Batch disambiguation
    sort(same_half_reps.begin(), same_half_reps.end());
    same_half_reps.erase(unique(same_half_reps.begin(), same_half_reps.end()), same_half_reps.end());

    while (!same_half_reps.empty()) {
        vector<int> next_reps;

        int si = 0;
        while (si < (int)same_half_reps.size()) {
            if (si + 1 >= (int)same_half_reps.size()) {
                int rep = same_half_reps[si];
                int v = -1;
                for (int i = 0; i < n; i++) {
                    if (Find(i) == Find(rep)) { v = vals[i]; break; }
                }
                for (int k = 0; k < half; k++) q[pos[k]] = v;
                int r = ask();
                for (int k = 0; k < half; k++) q[pos[k]] = 1;
                int h = (r == kc + 1) ? 0 : 1;
                for (int i = 0; i < n; i++) {
                    if (Find(i) == Find(rep)) half_known[i] = h;
                }
                si++;
                continue;
            }

            int rep1 = same_half_reps[si], rep2 = same_half_reps[si + 1];
            int v = -1, w = -1;
            for (int i = 0; i < n; i++) {
                if (Find(i) == Find(rep1) && v == -1) v = vals[i];
                if (Find(i) == Find(rep2) && w == -1) w = vals[i];
                if (v != -1 && w != -1) break;
            }

            for (int k = 0; k < half; k++) q[pos[k]] = v;
            for (int k = half; k < n; k++) q[pos[k]] = w;
            int r = ask();
            for (int k = 0; k < half; k++) q[pos[k]] = 1;
            for (int k = half; k < n; k++) q[pos[k]] = 1;

            if (r == kc + 2) {
                for (int i = 0; i < n; i++) {
                    if (Find(i) == Find(rep1)) half_known[i] = 0;
                    if (Find(i) == Find(rep2)) half_known[i] = 1;
                }
            } else if (r == kc) {
                for (int i = 0; i < n; i++) {
                    if (Find(i) == Find(rep1)) half_known[i] = 1;
                    if (Find(i) == Find(rep2)) half_known[i] = 0;
                }
            } else {
                Unite(rep1, rep2);
                next_reps.push_back(Find(rep1));
            }
            si += 2;
        }

        sort(next_reps.begin(), next_reps.end());
        next_reps.erase(unique(next_reps.begin(), next_reps.end()), next_reps.end());
        same_half_reps = next_reps;
    }

    vector<int> left_vals, right_vals;
    vector<int> left_pos(pos.begin(), pos.begin() + half);
    vector<int> right_pos(pos.begin() + half, pos.end());

    for (int i = 0; i < n; i++) {
        if (half_known[i] == 0) left_vals.push_back(vals[i]);
        else right_vals.push_back(vals[i]);
    }

    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
    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;

    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);

    solve(vals,pos);
    submit();
}