docker_space/frontier_cs_2/logs/gen_0.cpp

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;

int N, perm[1001], unk[1001], us, kc;

// Use a large output buffer
static char obuf[1 << 22];
static int opos;

inline void oflush() {
    fwrite_unlocked(obuf, 1, opos, stdout);
    opos = 0;
    fflush(stdout);
}

inline void ochar(char c) {
    obuf[opos++] = c;
}

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

// Pre-built query line. q[i] is the value for position i.
int q[1001];

// Output query and read result
inline 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;
}

inline void submit() {
    ochar('1');
    for (int i = 0; i < N; i++) { ochar(' '); oint(perm[i]); }
    ochar('\n');
    oflush();
    exit(0);
}

int bsearch_range(int v, int lo, int hi) {
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        for (int i = lo; i <= mid; i++) q[unk[i]] = v;
        int r = ask();
        for (int i = lo; i <= mid; i++) q[unk[i]] = 1;
        if (r == kc + 1) hi = mid; else lo = mid + 1;
    }
    return lo;
}

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 using bit queries
    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;
    us = 0;
    for (int i = 0; i < N; i++) if (i != p1 && i != p3) unk[us++] = i;
    for (int i = 0; i < N; i++) q[i] = 1;
    q[p1] = 1; q[p3] = 3;

    // Phase 2: Paired binary search
    vector<int> vals;
    vals.push_back(2);
    for (int v = 4; v <= N; v++) vals.push_back(v);

    int vi = 0;
    while (vi < (int)vals.size()) {
        if (us == 0) break;
        if (us == 1) {
            perm[unk[0]] = vals[vi]; q[unk[0]] = vals[vi];
            us = 0; kc++; vi++;
            continue;
        }

        int v = vals[vi];
        bool paired = (vi + 1 < (int)vals.size() && us >= 2);
        int w = paired ? vals[vi + 1] : -1;

        if (!paired) {
            int idx = bsearch_range(v, 0, us - 1);
            perm[unk[idx]] = v; q[unk[idx]] = v;
            for (int i = idx; i < us - 1; i++) unk[i] = unk[i + 1];
            us--; kc++; vi++;
            continue;
        }

        // Paired binary search
        int lo = 0, hi = us - 1;
        int idx_v = -1, idx_w = -1;

        while (idx_v < 0 || idx_w < 0) {
            if (hi == lo) break; // shouldn't happen with 2 values
            if (hi - lo == 1) {
                q[unk[lo]] = v;
                int r = ask();
                q[unk[lo]] = 1;
                if (r == kc + 1) { idx_v = lo; idx_w = hi; }
                else { idx_v = hi; idx_w = lo; }
                break;
            }

            int mid = (lo + hi) / 2;
            // Paired query: left=v, right=w
            for (int i = lo; i <= mid; i++) q[unk[i]] = v;
            for (int i = mid + 1; i <= hi; i++) q[unk[i]] = w;
            int r = ask();
            for (int i = lo; i <= mid; i++) q[unk[i]] = 1;
            for (int i = mid + 1; i <= hi; i++) q[unk[i]] = 1;

            if (r == kc + 2) {
                // v left, w right
                idx_v = bsearch_range(v, lo, mid);
                idx_w = bsearch_range(w, mid + 1, hi);
            } else if (r == kc) {
                // v right, w left
                idx_v = bsearch_range(v, mid + 1, hi);
                idx_w = bsearch_range(w, lo, mid);
            } else {
                // Same half - disambiguate
                for (int i = lo; i <= mid; i++) q[unk[i]] = v;
                int r2 = ask();
                for (int i = lo; i <= mid; i++) q[unk[i]] = 1;
                if (r2 == kc + 1) hi = mid; else lo = mid + 1;
            }
        }

        if (idx_v >= 0 && idx_w >= 0) {
            perm[unk[idx_v]] = v; q[unk[idx_v]] = v;
            perm[unk[idx_w]] = w; q[unk[idx_w]] = w;
            int r1 = idx_v, r2 = idx_w;
            if (r1 > r2) { int t = r1; r1 = r2; r2 = t; }
            for (int i = r2; i < us - 1; i++) unk[i] = unk[i + 1]; us--;
            for (int i = r1; i < us - 1; i++) unk[i] = unk[i + 1]; us--;
            kc += 2; vi += 2;
        } else {
            int idx = bsearch_range(v, 0, us - 1);
            perm[unk[idx]] = v; q[unk[idx]] = v;
            for (int i = idx; i < us - 1; i++) unk[i] = unk[i + 1];
            us--; kc++; vi++;
        }
    }

    if (us > 0) {
        for (int v = 1; v <= N; v++) {
            bool f = false;
            for (int i = 0; i < N; i++) if (perm[i] == v) { f = true; break; }
            if (!f) { perm[unk[--us]] = v; if (!us) break; }
        }
    }
    submit();
}