// This *might* be a valid solution. We need to decide if we want to reward it // or not. // // Randomly does 12 battles each, and anyone who didn't win a lot is eliminated. // Then sort. // // This passes with high probability if the judge data is fixed. #include #include using namespace std; const int NUM_BATTLES_EACH = 12; // Assumed to be even. const int MAX_INTERACTIONS = 100'000; #ifdef LOCAL #include vector secret_order; int total_interactions = 0; void preseed_fake_interactions(int n) { secret_order.resize(n); iota(secret_order.begin(), secret_order.end(), 0); auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count(); cerr << "Using seed: " << seed << endl; shuffle(secret_order.begin(), secret_order.end(), default_random_engine(seed)); } #endif vector perm; bool compare(int a, int b) { #ifdef LOCAL total_interactions++; return secret_order[perm[a]] < secret_order[perm[b]]; #endif cout << "? " << perm[a] << " " << perm[b] << endl; int better; cin >> better; if (better == -1) exit(0); return better == perm[a]; } void answer(vector a, int k) { #ifdef LOCAL if (total_interactions > MAX_INTERACTIONS) { cerr << "Too many interactions: " << total_interactions << endl; exit(1); } for (int x : a) { if (secret_order[perm[x]] >= k) { cerr << "Invalid answer: " << secret_order[perm[x]] << " >= " << k << endl; exit(1); } } if (a.size() != k) { cerr << "Wrong number of answers: " << a.size() << " vs " << k << endl; exit(1); } cerr << "Correct answer using " << total_interactions << " interactions" << endl; return; #endif cout << "!"; for (int x : a) cout << " " << perm[x]; cout << endl; } int main() { int n, k; cin >> n >> k; #ifdef LOCAL preseed_fake_interactions(n); #endif // Permute my output. perm.resize(n); iota(perm.begin(), perm.end(), 1); shuffle(perm.begin(), perm.end(), default_random_engine(12'344'445)); // Do a bunch of battles first vector wins(n); int so_far = 0; for (int i = 0; i < n; i++) { for (int j = 1; j <= NUM_BATTLES_EACH / 2; j++) { int opp = (i + j) % n; if (i == opp) continue; // If n is small, this can happen. wins[compare(i, opp) ? i : opp]++; so_far++; } } // Pick candidates until we have too many. vector candidates; for (int wins_needed = NUM_BATTLES_EACH; wins_needed >= 0; wins_needed--) { vector new_candidates; for (int i = 0; i < n; i++) if (wins[i] == wins_needed) new_candidates.push_back(i); int m = candidates.size() + new_candidates.size(); if (m > 0 && m * ceil(log2(m)) + so_far >= MAX_INTERACTIONS - 100) break; candidates.insert(candidates.end(), new_candidates.begin(), new_candidates.end()); } // Naive sort. (stable_ guarantees O(n log n)) stable_sort(candidates.begin(), candidates.end(), compare); candidates.resize(min(k, (int)candidates.size())); answer(candidates, k); }