docker_space/frontier_cs_2/solution_backup.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;
    }
    // n=3 handled by general D&C below (2 queries: 1 split + 1 for n=2)

    int half = n / 2;
    int right_half = n - half;

    for (int i = 0; i < n; i++) par[i] = i;

    vector<int> half_known(n, -1);
    int left_count = 0, right_count = 0;

    // Helper: assign a group (by representative) to a half
    auto assign_group = [&](int rep, int h) {
        for (int i = 0; i < n; i++) {
            if (Find(i) == Find(rep)) {
                half_known[i] = h;
                if (h == 0) left_count++;
                else right_count++;
            }
        }
    };

    // Helper: check if remaining undetermined values can be inferred
    auto check_early_termination = [&]() -> bool {
        if (left_count == half) {
            // All remaining go right
            for (int i = 0; i < n; i++) {
                if (half_known[i] == -1) { half_known[i] = 1; right_count++; }
            }
            return true;
        }
        if (right_count == right_half) {
            for (int i = 0; i < n; i++) {
                if (half_known[i] == -1) { half_known[i] = 0; left_count++; }
            }
            return true;
        }
        return false;
    };

    vector<int> same_half_reps;

    // Phase 1: pair values
    for (int vi = 0; vi + 1 < n; vi += 2) {
        if (check_early_termination()) break;

        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;
            left_count++; right_count++;
        } else if (r == kc) {
            half_known[vi] = 1; half_known[vi + 1] = 0;
            left_count++; right_count++;
        } else {
            Unite(vi, vi + 1);
            same_half_reps.push_back(Find(vi));
        }
    }

    // Handle odd value
    if (n % 2 == 1 && half_known[n-1] == -1) {
        if (check_early_termination()) goto done_disambiguation;
        int vi = n - 1;
        if (!same_half_reps.empty()) {
            int rep = same_half_reps.back();
            same_half_reps.pop_back();
            int v = vals[vi];
            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) {
                half_known[vi] = 0; left_count++;
                assign_group(rep, 1);
            } else if (r == kc) {
                half_known[vi] = 1; right_count++;
                assign_group(rep, 0);
            } else {
                Unite(vi, rep);
                same_half_reps.push_back(Find(vi));
            }
        } else {
            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;
            if (half_known[vi] == 0) left_count++; else right_count++;
        }
    }

    // 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()) {
        if (check_early_termination()) break;

        vector<int> next_reps;
        int si = 0;
        while (si < (int)same_half_reps.size()) {
            if (check_early_termination()) break;

            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;
                assign_group(rep, 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) {
                assign_group(rep1, 0);
                assign_group(rep2, 1);
            } else if (r == kc) {
                assign_group(rep1, 1);
                assign_group(rep2, 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;
    }

done_disambiguation:

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