File size: 5,014 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 | #include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> parent, sz;
DSU(int n) {
parent.resize(n+1);
sz.resize(n+1);
for (int i=1; i<=n; i++) parent[i] = i, sz[i] = 1;
}
int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
parent[b] = a;
sz[a] += sz[b];
return true;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int subtask, n;
cin >> subtask >> n;
// Determine number of bits needed
int L = 0;
while ((1 << L) <= n) L++;
// L queries
vector<int> b(n+1, 0); // b[i] will store the response bits as an integer
for (int bit = 0; bit < L; ++bit) {
vector<int> lst;
for (int i = 1; i <= n; ++i) {
if ((i >> bit) & 1) lst.push_back(i);
}
cout << lst.size();
for (int x : lst) cout << ' ' << x;
cout << endl;
cout.flush();
for (size_t idx = 0; idx < lst.size(); ++idx) {
int resp;
cin >> resp;
if (resp) b[lst[idx]] |= (1 << bit);
}
}
// Reconstruct the cycle
DSU dsu(n);
vector<int> degree(n+1, 0);
vector<bool> available(n+1, true); // degree < 2
vector<vector<int>> adj(n+1);
int edges_added = 0;
// Helper to enumerate submasks
auto enumerate_submasks = [&](int mask, vector<int>& out) {
out.clear();
int submask = mask;
while (submask) {
out.push_back(submask);
submask = (submask - 1) & mask;
}
out.push_back(0);
};
for (int i = 1; i <= n; ++i) {
int target = b[i];
vector<vector<int>> candidates;
if (target == 0) {
candidates.push_back({}); // empty set
} else {
// Single neighbor candidate
if (target <= n && target < i && available[target]) {
candidates.push_back({target});
}
// Pair candidates: enumerate first part
vector<int> submasks;
enumerate_submasks(target, submasks);
for (int s : submasks) {
if (s == 0) continue;
if (s > n || s >= i || !available[s]) continue;
int remaining = target ^ s; // bits in target not in s
// Now we need t such that (s | t) == target.
// t must have all bits of remaining, and can have any subset of s.
// Enumerate t_sub as submask of s
vector<int> t_subs;
enumerate_submasks(s, t_subs);
for (int t_sub : t_subs) {
int t = remaining | t_sub;
if (t == 0) continue;
if (t > n || t >= i || !available[t]) continue;
if (t == s) continue; // would be same as single
candidates.push_back({s, t});
}
}
}
// Filter candidates
vector<vector<int>> valid;
for (auto& S : candidates) {
// Check degree: already ensured by available[].
// Check cycle creation
int cycles = 0;
for (int j : S) {
if (dsu.find(i) == dsu.find(j)) cycles++;
}
if (cycles > 1) continue;
if (cycles == 1 && edges_added + (int)S.size() != n) continue;
if (edges_added + (int)S.size() > n) continue;
valid.push_back(S);
}
vector<int> chosen;
if (!valid.empty()) {
// Prefer larger sets to add more edges
for (auto& S : valid) {
if (S.size() == 2) {
chosen = S;
break;
}
}
if (chosen.empty()) chosen = valid[0];
} else {
// Fallback: assume no smaller neighbors if target==0, else assume target itself if possible.
if (target == 0) chosen = {};
else if (target <= n && target < i) chosen = {target};
else chosen = {};
}
// Add edges
for (int j : chosen) {
degree[i]++; degree[j]++;
adj[i].push_back(j);
adj[j].push_back(i);
dsu.unite(i, j);
if (degree[j] == 2) available[j] = false;
edges_added++;
}
if (degree[i] == 2) available[i] = false;
}
// Build the cycle starting from 1
vector<int> cycle;
cycle.push_back(1);
int prev = 1, cur = adj[1][0];
while (cur != 1) {
cycle.push_back(cur);
int nxt = (adj[cur][0] == prev) ? adj[cur][1] : adj[cur][0];
prev = cur;
cur = nxt;
}
cout << -1;
for (int x : cycle) cout << ' ' << x;
cout << endl;
cout.flush();
return 0;
} |