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

// kc: matches from positions NOT in pos[] (already correctly set in q[])
void solve(vector<int>& vals, vector<int>& pos, int kc) {
    int n = vals.size();
    if (n == 0) return;
    if (n == 1) {
        perm[pos[0]] = vals[0]; q[pos[0]] = vals[0];
        return;
    }
    if (n == 2) {
        // Set pos[0] to vals[0], pos[1] to some background from vals
        // Background for pos[1]: vals[0] is being tested at pos[0].
        // But what's at pos[1]? It's vals[0] or vals[1].
        // Set pos[0] = vals[0], pos[1] = vals[1] (test both)
        // Wait, for n=2 with the standard approach:
        // Set pos[0] = vals[0]. Leave pos[1] = whatever it was (background).
        // The background for pos[1] should NOT match perm[pos[1]].
        // perm[pos[1]] is either vals[0] or vals[1].
        // If bg is some value NOT in {vals[0], vals[1]}, no match.
        // But we might not have such a value available...
        //
        // Alternative: set pos[0] = vals[0], pos[1] = vals[0] too (both same value).
        // matches from pos[]: [perm[pos[0]] == vals[0]] + [perm[pos[1]] == vals[0]]
        // Exactly one of perm[pos[0]], perm[pos[1]] equals vals[0].
        // So internal matches = 1 always. No info!
        //
        // Better: set pos[0] = vals[0], pos[1] = vals[1].
        // matches = [perm[pos[0]] == vals[0]] + [perm[pos[1]] == vals[1]]
        // If correct: 2. If swapped: 0.
        // r = kc + 0 or kc + 2.
        q[pos[0]] = vals[0]; q[pos[1]] = vals[1];
        int r = ask();
        if (r == kc + 2) {
            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];
        }
        return;
    }
    if (n == 3) {
        q[pos[0]] = vals[0]; q[pos[1]] = vals[1]; q[pos[2]] = vals[2];
        int r1 = ask();
        int s1 = r1 - kc;
        if (s1 == 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];
            return;
        }
        q[pos[0]] = vals[0]; q[pos[1]] = vals[2]; q[pos[2]] = vals[1];
        int r2 = ask();
        int s2 = r2 - kc;
        if (s2 == 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];
            return;
        }
        if (s1 == 1 && s2 == 0) {
            q[pos[0]] = vals[1]; q[pos[1]] = vals[0]; q[pos[2]] = vals[0]; // only care about pos[0]
            // Hmm, need to be careful with pos[1] and pos[2]
            // Set pos[0] = vals[1], others = some safe bg
            // Safe bg: use vals[0] (it's at pos[0] or pos[1] or pos[2])
            // Actually for n=3, perm[pos[1]] and perm[pos[2]] are from {vals[0],vals[1],vals[2]}
            // If I set pos[1]=vals[0], it matches if perm[pos[1]]=vals[0].
            // I don't want noise from pos[1] and pos[2].
            // Set pos[1] and pos[2] to a value NOT in vals. But all values 1..N are possible.
            // The original approach (with kc from known positions outside) uses bg=1.
            // Here I don't have that luxury.
            //
            // BUT: at the top level, there are no external positions. At deeper levels,
            // external positions contribute to kc. The key is that pos[1] and pos[2]'s
            // q values should NOT match perm[pos[1]] and perm[pos[2]].
            //
            // For the disambiguation query, I only need pos[0] to be meaningful.
            // Set pos[0] = vals[1].
            // Set pos[1] = vals[2], pos[2] = vals[2].
            // matches from pos[]: [perm[pos[0]]==vals[1]] + [perm[pos[1]]==vals[2]] + [perm[pos[2]]==vals[2]]
            // In case (v1,v0,v2): pos[0]=v1, pos[1]=v0, pos[2]=v2.
            //   match pos[0]: v1==vals[1]? Yes! Match.
            //   match pos[1]: v0==vals[2]? No.
            //   match pos[2]: v2==vals[2]? Yes!
            //   Total internal: 2. r = kc + 2.
            // In case (v2,v1,v0): pos[0]=v2, pos[1]=v1, pos[2]=v0.
            //   match pos[0]: v2==vals[1]? No.
            //   match pos[1]: v1==vals[2]? No.
            //   match pos[2]: v0==vals[2]? No.
            //   Total internal: 0. r = kc + 0.
            // Distinguished! r == kc+2 -> (v1,v0,v2), r == kc -> (v2,v1,v0).

            q[pos[0]] = vals[1]; q[pos[1]] = vals[2]; q[pos[2]] = vals[2];
            int r3 = ask();
            if (r3 >= kc + 2) {
                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];
            }
            return;
        }
        if (s1 == 0 && s2 == 1) {
            // (v1,v2,v0) or (v2,v0,v1)
            q[pos[0]] = vals[1]; q[pos[1]] = vals[0]; q[pos[2]] = vals[0];
            int r3 = ask();
            // (v1,v2,v0): pos[0]=v1. match pos[0]: vals[1]==v1? Yes. + pos[1]=v2, q=vals[0], no. + pos[2]=v0, q=vals[0], yes!
            // Total: kc + 2.
            // (v2,v0,v1): pos[0]=v2. match: vals[1]==v2? No. + pos[1]=v0, q=vals[0], yes! + pos[2]=v1, q=vals[0], no.
            // Total: kc + 1.
            // Hmm, both give 1-2 matches, not cleanly 0 vs 2.
            // Let me recalculate:
            // (v1,v2,v0): [vals[1]==vals[1]]=1, [vals[0]==vals[2]]=0, [vals[0]==vals[0]]=1 -> 2
            // (v2,v0,v1): [vals[1]==vals[2]]=0, [vals[0]==vals[0]]=1, [vals[0]==vals[1]]=0 -> 1
            // Distinguished: kc+2 vs kc+1.
            if (r3 >= kc + 2) {
                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];
            }
            return;
        }
        // Unreachable
        return;
    }

    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;

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

    auto check_early = [&]() -> bool {
        if (left_count == half) {
            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;

    for (int vi = 0; vi + 1 < n; vi += 2) {
        if (check_early()) 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;
        int matches = r - kc;
        if (matches == 2) {
            half_known[vi] = 0; half_known[vi + 1] = 1;
            left_count++; right_count++;
        } else if (matches == 0) {
            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));
        }
    }

    if (n % 2 == 1 && half_known[n-1] == -1 && !check_early()) {
        int vi = n - 1;
        if (!same_half_reps.empty()) {
            int rep = same_half_reps.back();
            same_half_reps.pop_back();
            int v = vals[vi], 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;
            int matches = r - kc;
            if (matches == 2) { half_known[vi] = 0; left_count++; assign_group(rep, 1); }
            else if (matches == 0) { 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;
            int h = (r - kc == 1) ? 0 : 1;
            half_known[vi] = h;
            if (h==0) left_count++; else right_count++;
        }
    }

    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()) break;
        vector<int> next_reps;
        int si = 0;
        while (si < (int)same_half_reps.size()) {
            if (check_early()) 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;
                assign_group(rep, (r - kc == 1) ? 0 : 1);
                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;
            int matches = r - kc;
            if (matches == 2) { assign_group(rep1, 0); assign_group(rep2, 1); }
            else if (matches == 0) { 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;
    }

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

    // Set right positions to a safe background (a left value)
    // Right positions have values from right_vals. left_vals values won't match.
    int bg = left_vals.empty() ? 1 : left_vals[0];
    for (int i = 0; i < (int)right_pos.size(); i++) q[right_pos[i]] = bg;

    solve(left_vals, left_pos, kc);

    // After solving left, left positions are correctly set.
    // External kc for right = kc + left_vals.size()
    int new_kc = kc + left_vals.size();
    solve(right_vals, right_pos, new_kc);
}

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

    for(int i=0;i<N;i++) q[i]=1; // initial background

    vector<int> vals,pos;
    for(int v=1;v<=N;v++) vals.push_back(v);
    for(int i=0;i<N;i++) pos.push_back(i);

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