#include #include #include #include #include #include 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 query(const vector& ops) { if (ops.empty()) return {}; cout << ops.size(); for (int x : ops) { cout << " " << x; } cout << endl; vector res(ops.size()); for (int i = 0; i < ops.size(); ++i) { cin >> res[i]; } return res; } // Function to submit guess void guess(const vector& 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 remaining(n); iota(remaining.begin(), remaining.end(), 1); vector> 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 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 clear_ops; for (int u : S_curr) clear_ops.push_back(u); // Sequence: clear, then try adding candidates vector ops = clear_ops; vector 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 res = query(ops); // Update S_curr locally S_curr.clear(); // After clear_ops, S is empty vector current_C; vector 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 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 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 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 probes; int ops_offset = ops.size(); // index in result vector for (int i = 0; i < C.size(); ++i) { // Target set T vector 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 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 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 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 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 ops; // Clear S_curr for (int u : S_curr) ops.push_back(u); set S_sim; // simulated empty state struct ProbeIdx { int u; int res_idx; }; vector probe_indices; for (int i = 0; i < C.size(); ++i) { // T = C_i \cap {bit b == val} vector 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 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 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_{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}? // 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> 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, 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 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 ops; for (int u : S_curr) ops.push_back(u); set S_sim; struct ProbeIdx { int u; int target_layer; int res_idx; }; vector probe_indices; for (int i = 0; i < C.size(); ++i) { vector T; for (int u : C[i]) if (((u >> b) & 1) == val) T.push_back(u); vector 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 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 p; vector 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>& C) { // This function was needed in logic, but implementation changed. return false; }