docker_space/frontier_cs_3/solution_v4.cpp

#include <bits/stdc++.h>
using namespace std;

static int N;

static inline int readInt() {
    int c = getchar_unlocked();
    while (c != '-' && (c < '0' || c > '9')) {
        c = getchar_unlocked();
        if (c == EOF) return 0;
    }
    int sgn = 1;
    if (c == '-') { sgn = -1; c = getchar_unlocked(); }
    int x = 0;
    while (c >= '0' && c <= '9') { x = x*10+(c-'0'); c = getchar_unlocked(); }
    return x * sgn;
}

static char wbuf[1 << 23];
static int wpos = 0;
static void wflush() { if (wpos > 0) fwrite(wbuf, 1, wpos, stdout); wpos = 0; fflush(stdout); }
static void wchar(char c) { if (wpos >= (1<<23)-2) wflush(); wbuf[wpos++] = c; }
static void wint(long long x) {
    if (x < 0) { wchar('-'); x = -x; }
    if (x == 0) { wchar('0'); return; }
    char buf[20]; int len = 0;
    while (x > 0) { buf[len++] = '0'+(int)(x%10); x /= 10; }
    for (int i = len-1; i >= 0; i--) wchar(buf[i]);
}

static int resBuf[10000010];

static void doRound(const vector<int>& ops, int* res) {
    wint((int)ops.size());
    for (int x : ops) { wchar(' '); wint(x); }
    wchar('\n'); wflush();
    for (int i = 0; i < (int)ops.size(); i++) res[i] = readInt();
}

static void doRoundIgnore(const vector<int>& ops) {
    if (ops.empty()) return;
    doRound(ops, resBuf);
}

static int toggle1(int v) {
    wint(1); wchar(' '); wint(v); wchar('\n'); wflush();
    return readInt();
}

static mt19937 rng(42);

static void solve_small() {
    vector<int> ops;
    vector<pair<int,int>> pairs;
    for (int i = 1; i <= N; i++)
        for (int j = i+1; j <= N; j++) {
            ops.push_back(i); ops.push_back(j);
            ops.push_back(i); ops.push_back(j);
            pairs.push_back({i,j});
        }
    doRound(ops, resBuf);
    vector<vector<int>> adj(N+1);
    for (size_t k = 0; k < pairs.size(); k++)
        if (resBuf[4*k+1] == 1) {
            adj[pairs[k].first].push_back(pairs[k].second);
            adj[pairs[k].second].push_back(pairs[k].first);
        }
    vector<int> chain = {1};
    if (N > 1 && !adj[1].empty()) {
        chain.push_back(adj[1][0]);
        for (int i = 2; i < N; i++) {
            int last = chain.back(), prev = chain[chain.size()-2];
            for (int nb : adj[last])
                if (nb != prev) { chain.push_back(nb); break; }
        }
    }
    wint(-1);
    for (int v : chain) { wchar(' '); wint(v); }
    wchar('\n'); wflush();
}

// Build IS by batching individual toggles into rounds
// Process B candidates per round: toggle each on, read result, toggle off if bad
// This uses 1 round per batch of B candidates, with 2*B ops per round
// (vs 1-2 rounds per candidate in original)
static vector<int> buildIS_batched_toggles(vector<int> nodes, int batchSize) {
    if (nodes.empty()) return {};
    shuffle(nodes.begin(), nodes.end(), rng);

    vector<int> IS;
    set<int> inIS;

    int i = 0;
    while (i < (int)nodes.size()) {
        int end = min(i + batchSize, (int)nodes.size());
        // Build a round: for each candidate, toggle on then toggle off
        // If toggle-on returns 0: safe, keep it (toggle off then back on at end)
        // If toggle-on returns 1: adjacent, toggle off immediately

        // Actually we can't do "toggle on, check, decide, toggle off" in a single round
        // because we submit all ops at once and get all results at once.

        // Alternative: just toggle each candidate on then off, and check the on-result
        // If on-result is 0, the candidate is not adjacent to any current S member
        // Since S = current IS, this means candidate is not adjacent to any IS member

        vector<int> ops;
        for (int j = i; j < end; j++) {
            ops.push_back(nodes[j]);
            ops.push_back(nodes[j]);
        }
        doRound(ops, resBuf);

        // Collect candidates that are safe (not adjacent to IS)
        vector<int> safe;
        for (int j = 0; j < end - i; j++) {
            if (resBuf[2*j] == 0) {
                safe.push_back(nodes[i+j]);
            }
        }

        // Now add safe candidates to IS one by one... but that requires individual rounds
        // OR: use the batch prefix approach
        if (!safe.empty()) {
            shuffle(safe.begin(), safe.end(), rng);
            doRound(safe, resBuf);
            int j2 = (int)safe.size();
            for (int k = 0; k < (int)safe.size(); k++) {
                if (resBuf[k] == 1) { j2 = k; break; }
            }
            for (int k = 0; k < j2; k++) {
                IS.push_back(safe[k]);
                inIS.insert(safe[k]);
            }
            // Remove non-IS safe nodes
            if (j2 < (int)safe.size()) {
                vector<int> rem;
                for (int k = (int)safe.size()-1; k >= j2; k--)
                    rem.push_back(safe[k]);
                doRoundIgnore(rem);
            }
        }

        i = end;
    }

    return IS;
}

static void solve_large() {
    // Phase 1: Build IS using batched approach
    // Use batch size = N (all at once) for maximum round efficiency
    vector<int> allNodes(N);
    iota(allNodes.begin(), allNodes.end(), 1);

    // First pass: probe all nodes against empty S
    shuffle(allNodes.begin(), allNodes.end(), rng);

    // Round 1: Toggle all N nodes on. Find IS prefix.
    doRound(allNodes, resBuf);
    int j = N;
    for (int i = 0; i < N; i++) {
        if (resBuf[i] == 1) { j = i; break; }
    }

    vector<int> IS;
    set<int> isSet;
    for (int i = 0; i < j; i++) {
        IS.push_back(allNodes[i]);
        isSet.insert(allNodes[i]);
    }

    // Round 2: Remove non-IS nodes
    if (j < N) {
        vector<int> rem;
        for (int i = N-1; i >= j; i--) rem.push_back(allNodes[i]);
        doRoundIgnore(rem);
    }

    // Iteratively expand IS
    for (int iter = 0; iter < 500; iter++) {
        vector<int> remaining;
        for (int v : allNodes) if (!isSet.count(v)) remaining.push_back(v);
        if (remaining.empty()) break;

        // Probe remaining against IS
        {
            vector<int> ops;
            ops.reserve(2*remaining.size());
            for (int v : remaining) { ops.push_back(v); ops.push_back(v); }
            doRound(ops, resBuf);
        }

        vector<int> safe;
        for (int i = 0; i < (int)remaining.size(); i++) {
            if (resBuf[2*i] == 0) safe.push_back(remaining[i]);
        }
        if (safe.empty()) break;

        shuffle(safe.begin(), safe.end(), rng);
        doRound(safe, resBuf);
        int j2 = (int)safe.size();
        for (int i = 0; i < (int)safe.size(); i++) {
            if (resBuf[i] == 1) { j2 = i; break; }
        }
        for (int i = 0; i < j2; i++) {
            IS.push_back(safe[i]);
            isSet.insert(safe[i]);
        }
        if (j2 < (int)safe.size()) {
            vector<int> rem;
            for (int i = (int)safe.size()-1; i >= j2; i--)
                rem.push_back(safe[i]);
            doRoundIgnore(rem);
        }
        if (j2 == (int)safe.size()) break;
    }

    int m = (int)IS.size();

    vector<bool> inIS(N+1, false);
    for (int v : IS) inIS[v] = true;

    vector<int> nonIS;
    for (int v = 1; v <= N; v++) if (!inIS[v]) nonIS.push_back(v);
    int nm = (int)nonIS.size();

    // Phase 2: Binary identification using sum + sum-of-squares
    int bits_sum = 0;
    { int v = 2*m; while (v > 0) { bits_sum++; v >>= 1; } }
    bits_sum = max(bits_sum, 1);

    int bits_sq = 0;
    { long long v = 2LL*m*m; while (v > 0) { bits_sq++; v >>= 1; } }
    bits_sq = max(bits_sq, 1);

    vector<long long> labsq(m);
    for (int i = 0; i < m; i++) labsq[i] = (long long)(i+1)*(i+1);

    vector<bool> curLit(m, true);
    vector<long long> nsum(nm, 0), nsq(nm, 0);
    vector<int> carry_s(nm, 0), carry_q(nm, 0);
    int maxBits = max(bits_sum, bits_sq);

    for (int b = 0; b < maxBits; b++) {
        if (b < bits_sum) {
            vector<int> ops;
            ops.reserve(3*m + 4*nm);
            for (int i = 0; i < m; i++) {
                bool want = (((i+1)>>b)&1)==1;
                if (curLit[i] != want) { ops.push_back(IS[i]); curLit[i] = want; }
            }
            int po1 = (int)ops.size();
            for (int v : nonIS) { ops.push_back(v); ops.push_back(v); }
            for (int i = 0; i < m; i++) {
                bool want = (((i+1)>>b)&1)==0;
                if (curLit[i] != want) { ops.push_back(IS[i]); curLit[i] = want; }
            }
            int po2 = (int)ops.size();
            for (int v : nonIS) { ops.push_back(v); ops.push_back(v); }

            doRound(ops, resBuf);

            for (int j = 0; j < nm; j++) {
                int ho = resBuf[po1+2*j];
                int hz = resBuf[po2+2*j];
                int cnt = !ho ? 0 : !hz ? 2 : 1;
                int total = cnt + carry_s[j];
                if (total & 1) nsum[j] |= (1LL << b);
                carry_s[j] = total >> 1;
            }
        }
        if (b < bits_sq) {
            vector<int> ops;
            ops.reserve(3*m + 4*nm);
            for (int i = 0; i < m; i++) {
                bool want = ((labsq[i]>>b)&1)==1;
                if (curLit[i] != want) { ops.push_back(IS[i]); curLit[i] = want; }
            }
            int po1 = (int)ops.size();
            for (int v : nonIS) { ops.push_back(v); ops.push_back(v); }
            for (int i = 0; i < m; i++) {
                bool want = ((labsq[i]>>b)&1)==0;
                if (curLit[i] != want) { ops.push_back(IS[i]); curLit[i] = want; }
            }
            int po2 = (int)ops.size();
            for (int v : nonIS) { ops.push_back(v); ops.push_back(v); }

            doRound(ops, resBuf);

            for (int j = 0; j < nm; j++) {
                int ho = resBuf[po1+2*j], hz = resBuf[po2+2*j];
                int cnt = !ho ? 0 : !hz ? 2 : 1;
                int total = cnt + carry_q[j];
                if (total & 1) nsq[j] |= (1LL << b);
                carry_q[j] = total >> 1;
            }
        }
    }
    for (int j = 0; j < nm; j++) {
        if (carry_s[j]) nsum[j] |= ((long long)carry_s[j] << bits_sum);
        if (carry_q[j]) nsq[j] |= ((long long)carry_q[j] << bits_sq);
    }

    // Phase 3: Reconstruct edges
    vector<array<int,2>> adj(N+1, {0,0});
    vector<int> deg(N+1, 0);
    auto addEdge = [&](int u, int v) {
        if (u == v || u < 1 || u > N || v < 1 || v > N) return;
        if (deg[u] >= 2 || deg[v] >= 2) return;
        for (int k = 0; k < deg[u]; k++) if (adj[u][k] == v) return;
        adj[u][deg[u]++] = v;
        adj[v][deg[v]++] = u;
    };

    for (int j = 0; j < nm; j++) {
        long long S1 = nsum[j], S2 = nsq[j];
        if (S1 == 0 && S2 == 0) continue;
        long long disc = 2*S2 - S1*S1;
        if (disc < 0) continue;
        long long d = (long long)round(sqrt((double)disc));
        while (d > 0 && d*d > disc) d--;
        while ((d+1)*(d+1) <= disc) d++;
        if (d*d != disc) continue;
        if ((S1+d)%2 != 0) continue;
        long long la = (S1+d)/2, lb = (S1-d)/2;
        if (la >= 1 && la <= m) addEdge(nonIS[j], IS[la-1]);
        if (lb >= 1 && lb <= m && lb != la) addEdge(nonIS[j], IS[lb-1]);
    }

    // Phase 4: Handle remaining deg<2 nodes
    {
        vector<int> clearOps;
        for (int i = 0; i < m; i++)
            if (curLit[i]) { clearOps.push_back(IS[i]); curLit[i] = false; }
        if (!clearOps.empty()) doRoundIgnore(clearOps);
    }

    vector<int> deg1;
    for (int v : nonIS) if (deg[v] < 2) deg1.push_back(v);

    if (!deg1.empty()) {
        // Build IS2 using same batch approach
        // First need to clear S completely
        // S should already be empty after clearOps above

        vector<int> IS2;
        set<int> is2Set;

        // Batch IS building for deg1
        shuffle(deg1.begin(), deg1.end(), rng);
        vector<int> candidates = deg1;

        for (int iter = 0; iter < 300 && !candidates.empty(); iter++) {
            shuffle(candidates.begin(), candidates.end(), rng);
            doRound(candidates, resBuf);
            int j2 = (int)candidates.size();
            for (int i = 0; i < (int)candidates.size(); i++) {
                if (resBuf[i] == 1) { j2 = i; break; }
            }
            for (int i = 0; i < j2; i++) {
                IS2.push_back(candidates[i]);
                is2Set.insert(candidates[i]);
            }
            if (j2 < (int)candidates.size()) {
                vector<int> rem;
                for (int i = (int)candidates.size()-1; i >= j2; i--)
                    rem.push_back(candidates[i]);
                doRoundIgnore(rem);
            }
            if (j2 == (int)candidates.size()) break;

            vector<int> remaining;
            for (int v : candidates) if (!is2Set.count(v)) remaining.push_back(v);
            if (remaining.empty()) break;

            {
                vector<int> ops;
                ops.reserve(2*remaining.size());
                for (int v : remaining) { ops.push_back(v); ops.push_back(v); }
                doRound(ops, resBuf);
            }
            candidates.clear();
            for (int i = 0; i < (int)remaining.size(); i++) {
                if (resBuf[2*i] == 0) candidates.push_back(remaining[i]);
            }
        }

        int m2 = (int)IS2.size();
        vector<int> nonIS2;
        for (int v : deg1) if (!is2Set.count(v)) nonIS2.push_back(v);
        int nm2 = (int)nonIS2.size();

        if (m2 > 0 && nm2 > 0) {
            vector<bool> curLit2(m2, true);
            int bits2 = 0;
            { int v = m2; while (v > 0) { bits2++; v >>= 1; } }
            bits2 = max(bits2, 1);
            vector<int> nsum2(nm2, 0);

            for (int b = 0; b < bits2; b++) {
                vector<int> ops;
                ops.reserve(m2 + 2*nm2);
                for (int i = 0; i < m2; i++) {
                    bool want = (((i+1)>>b)&1)==1;
                    if (curLit2[i] != want) { ops.push_back(IS2[i]); curLit2[i] = want; }
                }
                int po = (int)ops.size();
                for (int v : nonIS2) { ops.push_back(v); ops.push_back(v); }
                doRound(ops, resBuf);
                for (int j = 0; j < nm2; j++)
                    if (resBuf[po+2*j]==1) nsum2[j] |= (1<<b);
            }
            for (int j = 0; j < nm2; j++) {
                int label = nsum2[j];
                if (label >= 1 && label <= m2) addEdge(nonIS2[j], IS2[label-1]);
            }
        }
    }

    // Traverse ring
    vector<int> order;
    order.reserve(N);
    int start = 1;
    for (int v = 1; v <= N; v++) if (deg[v] == 2) { start = v; break; }
    int prev = 0, cur = start;
    for (int i = 0; i < N; i++) {
        order.push_back(cur);
        int nxt = (adj[cur][0] != prev) ? adj[cur][0] : adj[cur][1];
        prev = cur; cur = nxt;
        if (cur == 0 || cur == start) break;
    }
    if ((int)order.size() != N) {
        order.clear();
        for (int v = 1; v <= N; v++) order.push_back(v);
    }
    wint(-1);
    for (int v : order) { wchar(' '); wint(v); }
    wchar('\n'); wflush();
}

int main() {
    int subtask = readInt();
    N = readInt();
    if (N <= 1) { wint(-1); wchar(' '); wint(1); wchar('\n'); wflush(); return 0; }
    if (N <= 1500) solve_small();
    else solve_large();
    return 0;
}