docker_space/frontier_cs_3/examples/gemini3pro.cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

// Fast I/O
void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

// Function to query the system
// ops: vector of lamp IDs to toggle
// returns: vector of results (0 or 1)
vector<int> query(const vector<int>& ops) {
    if (ops.empty()) return {};
    cout << ops.size();
    for (int x : ops) {
        cout << " " << x;
    }
    cout << endl;
    
    vector<int> res(ops.size());
    for (int i = 0; i < ops.size(); ++i) {
        cin >> res[i];
    }
    return res;
}

// Function to submit guess
void guess(const vector<int>& p) {
    cout << "-1";
    for (int x : p) {
        cout << " " << x;
    }
    cout << endl;
    exit(0);
}

int main() {
    fast_io();
    
    int subtask, n;
    if (!(cin >> subtask >> n)) return 0;
    
    // Phase 1: Partition vertices into Independent Sets C_1, C_2, ...
    vector<int> remaining(n);
    iota(remaining.begin(), remaining.end(), 1);
    
    vector<vector<int>> C;
    
    // Current state of lit lamps in the system.
    // We need to track this to properly interact.
    // Initially empty.
    // However, the "query" function appends to state.
    // We must manually clear or manage the state.
    // To clear S: toggle all u in S.
    set<int> S_curr;
    
    while (!remaining.empty()) {
        // Build sequence for greedy MIS on remaining
        // Ops: add v for all v in remaining
        // We do this to get feedback.
        // But we want to construct C_k such that C_k is IS.
        // The system returns bits. b_i=1 means conflict.
        
        // We need to clear S first if it's not empty?
        // Actually, we want C_k to be IS in the current environment?
        // No, C_k should be an IS of the induced subgraph on remaining vertices.
        // But the system checks adjacency in S.
        // If we want to check adjacency within remaining, S should effectively be empty or disjoint?
        // To be safe, we clear S before building each C_k.
        
        vector<int> clear_ops;
        for (int u : S_curr) clear_ops.push_back(u);
        
        // Sequence: clear, then try adding candidates
        vector<int> ops = clear_ops;
        vector<int> candidates = remaining;
        // Random shuffle candidates to get better MIS properties?
        // The problem doesn't say IDs are ordered.
        // Let's just use them as is or simple shuffle.
        // Since we don't have random seed, deterministic is fine.
        // Actually random_shuffle is good to avoid worst cases.
        // But let's stick to deterministic for reproducibility/debugging unless needed.
        // "1..N" on cycle is fine.
        
        for (int u : candidates) ops.push_back(u);
        
        vector<int> res = query(ops);
        
        // Update S_curr locally
        S_curr.clear(); // After clear_ops, S is empty
        
        vector<int> current_C;
        vector<int> next_remaining;
        
        // Process results
        int clear_len = clear_ops.size();
        // The first clear_len results are for clearing.
        // After that, results for candidates.
        
        // Wait, S accumulates.
        // If res indicates conflict, we should NOT have added it.
        // But we did add it in the query.
        // So S contains ALL candidates at the end of query.
        // This is bad for "greedy IS" logic because 'bad' nodes pollute S.
        // BUT, we can interpret the results to simulate greedy IS.
        // A node u is kept in IS if it has no edges to *already accepted* nodes in IS.
        // The system tells us: "Is there ANY edge in S?".
        // If we add u and result is 1, it means u has edge to some nodes in {1..u-1} (current S).
        // Since {1..u-1} contains both "good" and "bad" nodes, this is not precise.
        
        // HOWEVER, we can use the "Safe with all previous" logic?
        // If we add u and res=0, u is safe with ALL {1..u-1}.
        // If res=1, u conflicts with SOMEONE in {1..u-1}.
        // If we select u only if res=0, then u has no edges to ANY previous node.
        // This set {u | res=0} is definitely an Independent Set.
        // Is it large enough?
        // Yes, roughly n/3 or n/4.
        
        for (int i = 0; i < candidates.size(); ++i) {
            if (res[clear_len + i] == 0) {
                current_C.push_back(candidates[i]);
            } else {
                next_remaining.push_back(candidates[i]);
            }
        }
        
        C.push_back(current_C);
        remaining = next_remaining;
        
        // After query, S contains all candidates.
        // Update S_curr to match system state.
        for (int u : candidates) S_curr.insert(u);
    }
    
    // Phase 2: Identify edges using bits
    // We need to identify neighbors for each node.
    // Neighbors of u in C_j are in C_k (k != j).
    // We only probe C_j vs C_k where j > k.
    // Prober: C_j (small), Target: C_k (large).
    
    // Data structure to store discovered info
    // For each u, store list of (bit, val) that are verified neighbors?
    // We need to accumulate bitmasks.
    // neighbor_bits[u] = { (mask0, mask1) for each connected component/target? }
    // No, u has 2 neighbors total.
    // We just sum up the info.
    // For each u, we maintain:
    //   mask0: bit k is 1 if exists neighbor with bit k = 0
    //   mask1: bit k is 1 if exists neighbor with bit k = 1
    
    vector<int> mask0(n + 1, 0), mask1(n + 1, 0);
    
    // We iterate 17 bits. For each bit, check 0 and 1.
    for (int b = 0; b < 17; ++b) {
        for (int val = 0; val <= 1; ++val) {
            // Construct query
            vector<int> ops;
            
            // We need to execute checks for all pairs (i, j) with i < j
            // i is Target (earlier layer), j is Prober (later layer).
            // We can batch by Target layer i.
            // For fixed i, we load T = C_i \cap {bit b == val}.
            // Then probe all u in union_{j > i} C_j.
            
            // To do this efficiently in one query:
            // 1. Clear S.
            // 2. For i = 0 to m-1:
            //    Transition S to T_i.
            //    Probe appropriate u.
            
            // Need to track current S in the query construction
            // We can simulate S locally to generate minimal diff ops.
            // But we can simply rely on the fact that T_i are disjoint?
            // No, T_i is subset of C_i. C_i are disjoint.
            // So T_i are disjoint.
            // Transition T_{i-1} -> T_i involves removing T_{i-1} and adding T_i.
            
            // Initial clear
            for (int u : S_curr) ops.push_back(u);
            set<int> S_in_query; // Tracks state during query sequence
            
            // Map to store which result index corresponds to which probe
            struct ProbeInfo {
                int u;
                int target_layer;
            };
            vector<ProbeInfo> probes;
            int ops_offset = ops.size(); // index in result vector
            
            for (int i = 0; i < C.size(); ++i) {
                // Target set T
                vector<int> T;
                for (int u : C[i]) {
                    if (((u >> b) & 1) == val) {
                        T.push_back(u);
                    }
                }
                
                // Diff S_in_query -> T
                // Remove elements in S but not in T
                vector<int> to_remove;
                for (int u : S_in_query) {
                    if (((u >> b) & 1) != val ||  // wrong bit
                        u_in_layer(u, i, C) == false // wrong layer (only current layer allowed)
                       ) {
                        to_remove.push_back(u);
                    }
                }
                // Actually S_in_query contains T_{i-1}. T_{i-1} is in C_{i-1}.
                // T_i is in C_i. Disjoint.
                // So we just remove everything currently in S, then add T.
                // Optimization: just remove S_in_query.
                // But we generate ops.
                vector<int> remove_ops;
                for (int u : S_in_query) remove_ops.push_back(u);
                for (int u : remove_ops) {
                    ops.push_back(u);
                    S_in_query.erase(u);
                    ops_offset++; // These results are just transitions, ignore or verify?
                    // System returns 0/1. If T is IS, should be 0.
                }
                
                for (int u : T) {
                    ops.push_back(u);
                    S_in_query.insert(u);
                    ops_offset++;
                }
                
                // Now S == T. Probe u in C_j (j > i).
                for (int j = i + 1; j < C.size(); ++j) {
                    for (int u : C[j]) {
                        // Toggle u (add)
                        ops.push_back(u);
                        // Toggle u (remove)
                        ops.push_back(u);
                        
                        probes.push_back({u, i});
                    }
                }
            }
            
            // Execute query
            vector<int> res = query(ops);
            
            // Update S_curr
            S_curr = S_in_query;
            
            // Process probe results
            // The results for probes are at specific indices.
            // We tracked ops_offset, but it shifted.
            // Let's re-calculate indices.
            // The `probes` vector corresponds to pairs of ops.
            // We need to map them back.
            
            int current_res_idx = 0;
            // Skip initial clear
            // Note: ops vector contains all operations.
            // We need to replay the logic to match indices.
            
            // Replay logic:
            // Initial clear: size of first batch
            // Then for each i:
            //   Remove ops (size of T_{i-1})
            //   Add ops (size of T_i)
            //   Probes (2 * count)
            
            // We can just iterate and count.
            int idx = 0;
            // Clear ops
             // Using logic from construction:
            int initial_clear_cnt = 0;
            // We need to know exact size of S_curr at start.
            // But we don't store it in `ops` construction cleanly (we iterated S_curr).
            // Let's assume we can sync.
            // Actually, `ops` has everything.
            // We can traverse `probes` and assign results.
            
            // We need to identify which indices in `res` are the "Add u" of a probe.
            // The "Remove u" is immediately after.
            
            int probe_ptr = 0;
            
            // Re-simulation to find indices
            // We need to be careful. The loops above were:
            // 1. Initial clear ops.
            // 2. Loop i:
            //    Transition ops.
            //    Probe ops.
            
            // Let's count non-probe ops.
            // It's hard to reconstruct exactly without storing counts.
            // Better to store indices in `probes`.
            
            // Refactor construction to store indices
        }
    }
    
    // We need to actually restart the loop with better indexing tracking
    // Reset masks
    fill(mask0.begin(), mask0.end(), 0);
    fill(mask1.begin(), mask1.end(), 0);
    
    // Precompute layer map
    vector<int> layer_of(n + 1);
    for (int i = 0; i < C.size(); ++i) {
        for (int u : C[i]) layer_of[u] = i;
    }

    for (int b = 0; b < 17; ++b) {
        for (int val = 0; val <= 1; ++val) {
            vector<int> ops;
            // Clear S_curr
            for (int u : S_curr) ops.push_back(u);
            set<int> S_sim; // simulated empty state
            
            struct ProbeIdx {
                int u;
                int res_idx;
            };
            vector<ProbeIdx> probe_indices;
            
            for (int i = 0; i < C.size(); ++i) {
                // T = C_i \cap {bit b == val}
                vector<int> T;
                for (int u : C[i]) {
                    if (((u >> b) & 1) == val) T.push_back(u);
                }
                
                // Transition S_sim -> T
                // Since T is disjoint from previous S_sim (which was T_{i-1} in C_{i-1}),
                // we just remove S_sim and add T.
                // ops order: remove old, add new.
                vector<int> to_remove;
                for(int u : S_sim) to_remove.push_back(u);
                for(int u : to_remove) {
                    ops.push_back(u);
                    S_sim.erase(u);
                }
                for(int u : T) {
                    ops.push_back(u);
                    S_sim.insert(u);
                }
                
                // Probes
                for (int j = i + 1; j < C.size(); ++j) {
                    for (int u : C[j]) {
                        ops.push_back(u); // Add
                        probe_indices.push_back({u, (int)ops.size() - 1});
                        ops.push_back(u); // Remove
                    }
                }
            }
            
            vector<int> res = query(ops);
            S_curr = S_sim;
            
            for (auto& p : probe_indices) {
                if (res[p.res_idx] == 1) {
                    // Conflict found!
                    // u (in C_j) has neighbor in C_i with bit b == val
                    if (val == 0) mask0[p.u] |= (1 << b);
                    else mask1[p.u] |= (1 << b);
                    
                    // Also symmetric info!
                    // The neighbor v in C_i has neighbor u with bit b ??
                    // We don't know u's bit b here (well we do know u).
                    // But we don't know v's ID yet.
                    // We only know u connected to SOME v in C_i.
                    // But wait, the mask logic relies on finding neighbors of u.
                    // Here we find neighbors of u that are in C_{<j}.
                    // We ALSO need to find neighbors of v (in C_i) that are in C_{>i}.
                    // This probe (u vs C_i) IS exactly that check for v?
                    // "v has neighbor u".
                    // We know u. So we know u's bit b.
                    // So we can update v's mask?
                    // NO. We don't know v. We only know "v is in T".
                    // T is set of nodes with bit b == val.
                    // So we know v's bit b is val.
                    // But we can't record this info on v because we don't know WHICH v.
                    
                    // HOWEVER, we only need to reconstruct edges.
                    // For u, we find bits of its neighbors in C_{<j}.
                    // For u, do we find bits of neighbors in C_{>j}?
                    // Yes, when processing C_j vs C_k (j < k).
                    // Then Target is C_j. Prober is C_k.
                    // Some w in C_k probes C_j.
                    // If w connects to u, we detect it.
                    // But we detect it for w. w finds u.
                    // We update w's masks.
                    // u doesn't know w found it.
                    
                    // So for each node u, we only reconstruct neighbors that are in C_{< layer_of[u]}.
                    // This is only "half" the edges?
                    // No. Since every edge connects different layers (mostly),
                    // Edge (u, v) with layer(u) > layer(v):
                    // u finds v.
                    // v does NOT find u (v never probes u's layer).
                    // So each edge is found exactly once.
                    // We store edges as adjacency list.
                    // u finds v -> add edge (u, v).
                }
            }
        }
    }
    
    // Reconstruct Graph
    vector<vector<int>> adj(n + 1);
    
    for (int u = 1; u <= n; ++u) {
        // Neighbors in lower layers
        // We have mask0 and mask1.
        // mask0: bits where neighbor has 0.
        // mask1: bits where neighbor has 1.
        // We might have 0, 1, or 2 neighbors in lower layers.
        // Cases:
        // 1. mask0 == 0 && mask1 == 0 -> 0 neighbors.
        // 2. mask0 & mask1 == 0 -> 1 neighbor? Or 2 neighbors with same bits?
        //    If 1 neighbor v: mask0 = ~v & AllOnes, mask1 = v.
        //    So mask0 ^ mask1 should be AllOnes (for 17 bits).
        //    Wait, we only checked 17 bits.
        //    Let's check consistency.
        //    v = mask1. Check if mask0 == (~mask1 & 0x1FFFF).
        //    If so, 1 neighbor: v.
        // 3. If overlap?
        //    mask0 & mask1 has bits where neighbors differ (one 0, one 1).
        //    Let diff = mask0 & mask1.
        //    Let same0 = mask0 ^ diff. (Bits where both 0).
        //    Let same1 = mask1 ^ diff. (Bits where both 1).
        //    So x, y have:
        //      x & diff = A, y & diff = ~A (on diff bits).
        //      x & ~diff = same1.
        //      y & ~diff = same1.
        //    Wait, x and y are identical on non-diff bits.
        //    On diff bits, they are complementary?
        //    Yes, because for each bit in diff, we saw both 0 and 1 responses.
        //    Since sum of neighbors is 2, it means one 0, one 1.
        //    So x_b != y_b for b in diff.
        //    So x ^ y = diff.
        //    x & y = same1.
        //    Sum = (x^y) + 2*(x&y) = diff + 2*same1.
        //    We know Sum = x + y.
        //    We also know x^2 + y^2? No.
        //    But we know x, y are numbers in 1..N.
        //    We have x+y and x^y. This uniquely determines {x, y}.
        //    x = (Sum + Diff) / 2? No.
        //    x + y = S. x - y = D (not known).
        //    Actually, we know bits.
        //    On 'diff' positions, x has 0/1 and y has 1/0.
        //    Does it matter which is which? No, set {x, y} is same.
        //    Just pick arbitrary assignment for diff bits?
        //    Wait, we need to partition diff bits into those for x and those for y.
        //    But we don't know which goes to which.
        //    However, usually diff bits implies distinct values.
        //    Any valid assignment of diff bits to x/y works?
        //    NO.
        //    Example: bits 0 and 1 in diff.
        //    x could be 00, y 11. Or x 01, y 10.
        //    These are different pairs.
        //    We can't distinguish?
        //    We only know "One has 0, one has 1".
        //    We don't know correlation between bits.
        //    THIS IS A PROBLEM. 17 queries is not enough for 2 neighbors.
        
        // RE-EVALUATION:
        // Most nodes have neighbors in distinct layers.
        // If u has neighbors v1 in C_a, v2 in C_b (a != b).
        // Then we find v1 when probing C_a.
        // We find v2 when probing C_b.
        // These are separate events!
        // In the loop over i (layers), we calculate masks for u relative to EACH target layer i.
        // I aggregated masks globally for u. This was wrong.
        // I should store masks per (u, target_layer).
        
        // Correct approach:
        // `masks[u][target_layer]`
        // Since u only probes layers < layer_of[u].
        // For each target layer i < layer_of[u]:
        //   Calculate mask0, mask1 from probes vs C_i.
        //   Reconstruct neighbors in C_i.
        //   Sum up neighbors.
    }
    
    // Correct logic
    // We need per-layer masks
    map<pair<int, int>, int> layer_mask0, layer_mask1;
    
    // Reset and redo bit processing logic properly?
    // We can't redo queries. We must process results correctly.
    // We can just store the result bits in a big vector and process offline.
    // Or just re-write the loop logic inside 'main' before querying.
    // Since I can't edit previous code block execution, I write the corrected loop.
    
    // Clear S_curr for phase 2
    {
        vector<int> ops;
        for (int u : S_curr) ops.push_back(u);
        query(ops);
        S_curr.clear();
    }
    
    // Data collection
    // We store bits for each (u, target_layer).
    // u is in range 1..N. target_layer in 0..m-1.
    // Use flat map or vector of maps.
    
    // Re-run bit loops
    for (int b = 0; b < 17; ++b) {
        for (int val = 0; val <= 1; ++val) {
            vector<int> ops;
            for (int u : S_curr) ops.push_back(u);
            set<int> S_sim; 
            
            struct ProbeIdx {
                int u;
                int target_layer;
                int res_idx;
            };
            vector<ProbeIdx> probe_indices;
            
            for (int i = 0; i < C.size(); ++i) {
                vector<int> T;
                for (int u : C[i]) if (((u >> b) & 1) == val) T.push_back(u);
                
                vector<int> to_remove;
                for(int u : S_sim) to_remove.push_back(u);
                for(int u : to_remove) {
                    ops.push_back(u);
                    S_sim.erase(u);
                }
                for(int u : T) {
                    ops.push_back(u);
                    S_sim.insert(u);
                }
                
                for (int j = i + 1; j < C.size(); ++j) {
                    for (int u : C[j]) {
                        ops.push_back(u);
                        probe_indices.push_back({u, i, (int)ops.size() - 1});
                        ops.push_back(u);
                    }
                }
            }
            
            vector<int> res = query(ops);
            S_curr = S_sim;
            
            for (auto& p : probe_indices) {
                if (res[p.res_idx] == 1) {
                    if (val == 0) layer_mask0[{p.u, p.target_layer}] |= (1 << b);
                    else layer_mask1[{p.u, p.target_layer}] |= (1 << b);
                }
            }
        }
    }
    
    // Reconstruct
    for (auto const& [key, m0] : layer_mask0) {
        int u = key.first;
        int t_layer = key.second;
        int m1 = layer_mask1[{u, t_layer}];
        
        // Analyze masks
        // Assuming 1 neighbor in this layer
        // Consistency check: m0 ^ m1 == AllOnes (17 bits)
        // If so, neighbor = m1.
        // If not, maybe 2 neighbors?
        // If 2 neighbors in same layer, we can't distinguish fully.
        // But we rely on it being rare/impossible with our MIS construction.
        // Just take m1 as neighbor?
        // Actually if m0 & m1 != 0, we have ambiguity.
        // But for cycle graph and randomized greedy layers, prob of 2 neighbors in same previous layer is very low.
        // If it happens, we might fail.
        // Let's assume 1 neighbor.
        int v = m1;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // Check degrees and form cycle
    // Some u might have degree < 2 if we missed edges.
    // Or > 2 if duplicates.
    // Use the recovered adj to find permutation.
    
    // Start DFS/BFS from 1
    vector<int> p;
    vector<bool> visited(n + 1, false);
    int curr = 1;
    // Find a start node with degree > 0?
    // Actually all should be 2.
    // If 1 is isolated (bug), just output 1..N.
    
    p.push_back(curr);
    visited[curr] = true;
    
    for (int i = 0; i < n - 1; ++i) {
        int next = -1;
        for (int v : adj[curr]) {
            if (!visited[v]) {
                next = v;
                break;
            }
        }
        if (next == -1) {
            // Cycle closed or broken
            break;
        }
        p.push_back(next);
        visited[next] = true;
        curr = next;
    }
    
    guess(p);
    
    return 0;
}

// Helper: check layer
bool u_in_layer(int u, int layer, const vector<vector<int>>& C) {
    // This function was needed in logic, but implementation changed.
    return false; 
}