// gemini お試し 3 #include #include #include #include using namespace std; int N; vector A_fixed; // 確定済みの数列 map counts; // 各数字の残りの出現回数 // クエリ送信 // キャッシュなどは特にせず、素直に実装します bool ask(const vector& B) { if (B.empty()) return true; cout << "? " << B.size(); for (int b : B) { cout << " " << b; } cout << endl; string res; cin >> res; return res == "Yes"; } // u が v より「先」に来るか判定する // 前提: u != v, counts[u] > 0, counts[v] > 0 bool is_before(int u, int v) { if (u == v) return false; // クエリ B = (確定済みprefix) + (u) + (v を残り全個数) // 論理: // u が v より先なら、最初の u をマッチした後、残りの v が全てマッチする -> Yes // v が u より先なら、u を探すために最初の v をスキップしてしまうため、 // その後の v の個数が足りなくなる -> No vector B = A_fixed; B.push_back(u); int cnt_v = counts[v]; for (int k = 0; k < cnt_v; ++k) { B.push_back(v); } return ask(B); } int main() { // 入出力の高速化(念のため) cin.tie(NULL); ios::sync_with_stdio(false); if (!(cin >> N)) return 0; // --- フェーズ1: 楽観的な個数カウント --- vector existing; int total_count = 0; // 1. まず存在だけを確認し、個数を仮に1とする for (int v = 1; v <= N; ++v) { if (ask({v})) { counts[v] = 1; existing.push_back(v); total_count++; } else { counts[v] = 0; } // 既にN個見つかっていれば終了(順列ケースでの最適化) if (total_count == N) break; } // 2. 合計が N に満たない場合のみ、追加の個数を探索する if (total_count < N) { for (int v : existing) { int current = counts[v]; // まず current + 1 個あるか確認 vector q(current + 1, v); if (!ask(q)) { // これ以上ない。確定。 continue; } // current + 1 個以上ある場合、指数探索 + 二分探索 // 範囲 [low, high] int low = current + 1; int high = N; // 上限は N (もっと厳しくできるがこれで十分) // 指数探索で上限を絞る int sz = current * 2; while (sz <= N) { vector q2(sz, v); if (ask(q2)) { low = sz; sz *= 2; } else { high = sz - 1; break; } } // 二分探索で最大値を見つける // low は存在確認済み int ans = low; int l = low, r = high; while (l <= r) { if (l == r) { ans = l; break; } int mid = l + (r - l + 1) / 2; // 上側丸めで無限ループ防止 vector qm(mid, v); if (ask(qm)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } int diff = ans - counts[v]; counts[v] = ans; total_count += diff; if (total_count == N) break; } } // --- フェーズ2: 順序の特定 --- // 候補リストを作成 vector candidates = existing; // 比較関数 auto comp = [&](int a, int b) { return is_before(a, b); }; // マージソート(stable_sort)で初期順序を決定 // 比較回数は O(K log K) stable_sort(candidates.begin(), candidates.end(), comp); // 数列を復元 for (int i = 0; i < N; ++i) { // ソート済みリストの先頭が次の要素 int best = candidates[0]; candidates.erase(candidates.begin()); A_fixed.push_back(best); counts[best]--; // まだ残っていれば、正しい位置に再挿入 if (counts[best] > 0) { // 二分探索で挿入位置を探す auto it = lower_bound(candidates.begin(), candidates.end(), best, comp); candidates.insert(it, best); } } // 出力 cout << "!"; for (int a : A_fixed) { cout << " " << a; } cout << endl; return 0; }