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

    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_termination = [&]() -> 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;

    // 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);
            int fr = Find(vi);
            // Group of size 2 - check if forced
            if (left_count + 2 > half) {
                assign_group(fr, 1);
            } else if (right_count + 2 > right_half) {
                assign_group(fr, 0);
            } else {
                same_half_reps.push_back(fr);
            }
        }
    }

    // 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);
                int fr = Find(vi);
                int gsz = 0;
                for (int i = 0; i < n; i++) if (Find(i) == fr) gsz++;
                if (left_count + gsz > half) {
                    assign_group(fr, 1);
                } else if (right_count + gsz > right_half) {
                    assign_group(fr, 0);
                } else {
                    same_half_reps.push_back(fr);
                }
            }
        } 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: Cascading disambiguation - pair ambiguous groups together
    {
        // Deduplicate
        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());

        // Pre-cascade subset-sum check
        if (!same_half_reps.empty() && (int)same_half_reps.size() <= 20 && !check_early_termination()) {
            vector<int> gsizes;
            vector<int> greps;
            for (int rep : same_half_reps) {
                int fr = Find(rep);
                if (half_known[fr] != -1) continue;
                int gsz = 0;
                for (int i = 0; i < n; i++)
                    if (Find(i) == fr && half_known[i] == -1) gsz++;
                gsizes.push_back(gsz);
                greps.push_back(fr);
            }
            int ng = gsizes.size();
            int left_need = half - left_count;
            if (ng > 0 && left_need >= 0) {
                // For each group, check if forced
                for (int g = 0; g < ng; g++) {
                    if (half_known[greps[g]] != -1) continue;
                    vector<bool> can_without(left_need + 1, false);
                    can_without[0] = true;
                    for (int g2 = 0; g2 < ng; g2++) {
                        if (g2 == g || half_known[greps[g2]] != -1) continue;
                        for (int s = left_need; s >= gsizes[g2]; s--)
                            if (can_without[s - gsizes[g2]]) can_without[s] = true;
                    }
                    bool can_be_right = can_without[left_need];
                    bool can_be_left = (left_need >= gsizes[g]) && can_without[left_need - gsizes[g]];
                    if (can_be_left && !can_be_right) assign_group(greps[g], 0);
                    else if (can_be_right && !can_be_left) assign_group(greps[g], 1);
                }
                // Update same_half_reps
                vector<int> still;
                for (int rep : same_half_reps) {
                    int fr = Find(rep);
                    if (half_known[fr] == -1 && half_known[rep] == -1) still.push_back(fr);
                }
                sort(still.begin(), still.end());
                still.erase(unique(still.begin(), still.end()), still.end());
                same_half_reps = still;
            }
        }

        int max_rounds = 20; // safety limit
        while (!same_half_reps.empty() && max_rounds-- > 0) {
            if (check_early_termination()) break;

            // Remove already-resolved
            {
                vector<int> unresolved;
                for (int rep : same_half_reps) {
                    int fr = Find(rep);
                    if (half_known[fr] == -1 && half_known[rep] == -1)
                        unresolved.push_back(fr);
                }
                // Deduplicate
                sort(unresolved.begin(), unresolved.end());
                unresolved.erase(unique(unresolved.begin(), unresolved.end()), unresolved.end());
                same_half_reps = unresolved;
            }
            if (same_half_reps.empty()) 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()) {
                    // Single group - individual query
                    int rep = same_half_reps[si];
                    if (half_known[Find(rep)] != -1) { si++; continue; }
                    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;
                }

                // Pair two ambiguous groups together
                int rep1 = same_half_reps[si], rep2 = same_half_reps[si + 1];
                if (half_known[Find(rep1)] != -1) { si++; continue; }
                if (half_known[Find(rep2)] != -1) { si++; continue; }

                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 {
                    // Still ambiguous - unite and try again
                    Unite(rep1, rep2);
                    int fr = Find(rep1);
                    // Count group size
                    int gsz = 0;
                    for (int i = 0; i < n; i++)
                        if (Find(i) == fr) gsz++;
                    // Check if group is forced to one side
                    if (left_count + gsz > half) {
                        // Can't fit in left, must go right
                        assign_group(fr, 1);
                    } else if (right_count + gsz > right_half) {
                        // Can't fit in right, must go left
                        assign_group(fr, 0);
                    } else {
                        next_reps.push_back(fr);
                    }
                }
                si += 2;
            }

            // Deduplicate next round
            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;

            // Check if remaining groups have a unique valid assignment
            if (!same_half_reps.empty() && same_half_reps.size() <= 20) {
                // Compute group sizes
                vector<int> gsizes;
                for (int rep : same_half_reps) {
                    if (half_known[Find(rep)] != -1) continue;
                    int gsz = 0;
                    for (int i = 0; i < n; i++)
                        if (Find(i) == Find(rep) && half_known[i] == -1) gsz++;
                    gsizes.push_back(gsz);
                }
                int left_need = half - left_count;
                int right_need = right_half - right_count;

                // Try to find all valid subset-sum partitions
                // Use bitmask DP for small number of groups
                int ng = gsizes.size();
                if (ng > 0 && ng <= 20) {
                    // For each group, compute which assignment (left or right) works
                    // Find all subsets of groups that sum to left_need
                    vector<bool> can_sum(left_need + 1, false);
                    can_sum[0] = true;
                    for (int g = 0; g < ng; g++) {
                        for (int s = left_need; s >= gsizes[g]; s--) {
                            if (can_sum[s - gsizes[g]]) can_sum[s] = true;
                        }
                    }

                    if (can_sum[left_need]) {
                        // Count number of valid subsets
                        // For each group, check if it's ALWAYS in left, ALWAYS in right, or ambiguous
                        // A group is always-left if: removing it makes left_need-gsz unreachable
                        // A group is always-right if: it can never be in a valid left subset

                        for (int g = 0; g < ng; g++) {
                            int rep = same_half_reps[g];
                            if (half_known[Find(rep)] != -1) continue;

                            // Check if group g is always in the left subset
                            // Compute can_sum WITHOUT group g
                            vector<bool> can_without(left_need + 1, false);
                            can_without[0] = true;
                            for (int g2 = 0; g2 < ng; g2++) {
                                if (g2 == g) continue;
                                for (int s = left_need; s >= gsizes[g2]; s--) {
                                    if (can_without[s - gsizes[g2]]) can_without[s] = true;
                                }
                            }

                            bool can_be_right = can_without[left_need]; // left_need achievable without g
                            bool can_be_left = (left_need >= gsizes[g]) && can_without[left_need - gsizes[g]];

                            if (can_be_left && !can_be_right) {
                                assign_group(rep, 0); // must be left
                            } else if (can_be_right && !can_be_left) {
                                assign_group(rep, 1); // must be right
                            }
                        }

                        // Remove resolved groups
                        vector<int> still_unresolved;
                        for (int rep : same_half_reps) {
                            if (half_known[Find(rep)] == -1)
                                still_unresolved.push_back(rep);
                        }
                        same_half_reps = still_unresolved;
                    }
                }
            }
        }
    }

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