docker_space/frontier_cs_2/logs/gen_2.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);}

// Determine which half (left=true, right=false) each value's position is in.
// vals: values to assign. pos: positions, split at 'half' (left=[0..half-1], right=[half..n-1]).
// Returns: for each value in vals, true if in left half, false if in right half.
void assign_halves(vector<int>& vals, vector<int>& pos, int half, vector<bool>& is_left) {
    int n = vals.size();
    is_left.resize(n);

    // Phase 1: pair up values and do paired queries
    // Track same-half pairs for batched disambiguation
    vector<int> determined; // indices into vals that are determined
    vector<pair<int,int>> same_half_pairs; // pairs of indices that are in the same half

    int vi = 0;
    while (vi < n) {
        if (vi + 1 >= n) {
            // Odd value out - query directly
            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;
            is_left[vi] = (r == kc + 1);
            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 < (int)pos.size(); i++) q[pos[i]] = w;
        int r = ask();
        for (int i = 0; i < half; i++) q[pos[i]] = 1;
        for (int i = half; i < (int)pos.size(); i++) q[pos[i]] = 1;

        if (r == kc + 2) {
            is_left[vi] = true;
            is_left[vi + 1] = false;
        } else if (r == kc) {
            is_left[vi] = false;
            is_left[vi + 1] = true;
        } else {
            // Same half - defer disambiguation
            same_half_pairs.push_back({vi, vi + 1});
        }
        vi += 2;
    }

    // Phase 2: Batch disambiguation of same-half pairs.
    // Each pair (i,j) means vals[i] and vals[j] are in the same half.
    // We need to determine which half.
    // Strategy: pair up these pairs and use paired queries on representatives.

    while (!same_half_pairs.empty()) {
        vector<pair<int,int>> next_round;

        int si = 0;
        while (si < (int)same_half_pairs.size()) {
            if (si + 1 >= (int)same_half_pairs.size()) {
                // Odd pair - query directly
                auto [i, j] = same_half_pairs[si];
                int v = vals[i];
                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;
                bool left = (r == kc + 1);
                is_left[i] = left;
                is_left[j] = left;
                si++;
                continue;
            }

            // Pair two same-half pairs and query
            auto [i1, j1] = same_half_pairs[si];
            auto [i2, j2] = same_half_pairs[si + 1];
            int v = vals[i1], w = vals[i2];

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

            if (r == kc + 2) {
                // v in left, w in right
                is_left[i1] = true; is_left[j1] = true;
                is_left[i2] = false; is_left[j2] = false;
            } else if (r == kc) {
                // v in right, w in left
                is_left[i1] = false; is_left[j1] = false;
                is_left[i2] = true; is_left[j2] = true;
            } else {
                // Same half again! All 4 values in same half.
                // Group them: (i1,j1,i2,j2) all in same half.
                // For next round, treat as a single "super pair" with representative i1.
                // Actually, just pair them again: one representative per group.
                // We know i1,j1,i2,j2 all in same half.
                // Create a new pair entry for the next round.
                // Use i1 as representative for the group of 4.
                // Store all 4 indices somewhere.
                // Actually, let's just store one representative per group and a list of dependents.
                // For simplicity, just re-add (i1, i2) as a pair with j1,j2 as dependents.
                // When we determine i1's half, set j1,i2,j2 to the same.

                // Simple approach: mark j1 and j2 as depending on i1 and i2 respectively.
                // But they're already co-located. Let me just re-add as a single group.

                // For the next round, (i1, i2) is a same-half pair.
                // i1 carries j1 as a dependent. i2 carries j2.
                // When i1's half is determined, so is j1, i2, j2.

                // Simplest: just track that i1 and i2 are in the same half.
                // j1 and j2 are already known to be in the same half as i1 and i2 respectively.
                // So all 4 are in the same half.
                // Add (i1, i2) to next_round. When resolved, set all 4.

                // But we need to propagate: when i1 is determined, also set j1, i2, j2.
                // This requires tracking the groups.

                // Simplest implementation: use Union-Find to group all co-half values.
                // Then in each round, pick one representative per group and pair them.

                next_round.push_back({i1, i2});
                // All 4 will be in the same half. When (i1,i2) is resolved in a future round,
                // we need is_left[i1]=is_left[j1]=is_left[i2]=is_left[j2].
                // Since j1 is already linked to i1 and j2 to i2, we just need i1 and i2 to be resolved.
                // In the next round, (i1,i2) is a same-half pair. When it's determined,
                // is_left[i1] = is_left[i2] = some value. Then j1 and j2 also get that value.

                // But wait, is_left[j1] should already be set to the same as is_left[i1] from the original same_half_pairs entry.
                // Hmm, is_left[j1] hasn't been set yet (it's uninitialized for same_half entries).
            }
            si += 2;
        }
        same_half_pairs = next_round;
    }

    // Now propagate: for each original same-half pair (i,j), set is_left[j] = is_left[i].
    // But the propagation is implicit in the batched resolution above.
    // Wait - I only set is_left for the FIRST index of each pair when resolving.
    // Need to also set the second index.
    // Actually, in the code above, when we resolve a pair (i1,i2) from the next_round,
    // we set is_left[i1] and is_left[i2] directly. And the j1,j2 from the original pairs
    // are NOT set.

    // BUG: I need to propagate is_left from representatives to all group members.
    // This requires a proper Union-Find or group tracking.
}

// Hmm, this is getting complicated. Let me use Union-Find.

int parent[1001];
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
void unite(int a, int b) { parent[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;
    }

    int half = n / 2;

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

    // Determine which half each value is in
    vector<int> half_known(n, -1); // -1=unknown, 0=left, 1=right

    // Phase 1: pair values, do paired queries
    vector<int> same_half_reps; // representatives of same-half groups

    // Initial pairing: consecutive pairs
    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 {
            // Same half
            unite(vi, vi + 1);
            same_half_reps.push_back(find(vi));
        }
    }

    // Handle odd value
    if (n % 2 == 1) {
        int vi = n - 1;
        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
    // Deduplicate same_half_reps
    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()) {
                // Odd group - query directly
                int rep = same_half_reps[si];
                // Find any value in this group
                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) {
                // Group 1 in left, group 2 in right
                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 {
                // Same half again - merge groups
                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;
    }

    // Split into left and right
    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();
}