// gemini お試し #include #include #include #include #include #include using namespace std; // グローバル変数として保持 int N; vector A; // 現在確定している数列 map counts; // 各数字の残りの出現回数 // クエリを投げる関数 bool ask(const vector& B) { cout << "? " << B.size(); for (int b : B) { cout << " " << b; } cout << endl; string res; cin >> res; return res == "Yes"; } // u が v より先に来るか判定する関数 // 前提: u, v は共に残り回数が 1 以上である bool is_before(int u, int v) { if (u == v) return false; // 同じ値の比較は不要(実装上false扱い) // クエリ B = (確定済みprefix) + (u) + (v を counts[v] 個) vector B = A; B.push_back(u); for (int k = 0; k < counts[v]; ++k) { B.push_back(v); } return ask(B); } int main() { cin >> N; // フェーズ1: 各数字の出現回数をカウント // 制約的に 2N 回程度のクエリで済む for (int v = 1; v <= N; ++v) { // まず1個あるか確認 if (!ask({v})) { counts[v] = 0; continue; } // 1個あるなら、増やしていく int current_cnt = 1; while (true) { // v を current_cnt + 1 個送る // 最適化: 以前の結果を利用するなら二分探索もありだが、 // 総数がNなので線形探索で十分 (平均的なならし計算量は小さい) // 今回は単純に current_cnt+1 個の v を投げる vector q(current_cnt + 1, v); if (ask(q)) { current_cnt++; } else { break; } } counts[v] = current_cnt; } // フェーズ2: 順序の決定 // 候補となる数字(count > 0)を管理する vector candidates; for (auto const& [val, cnt] : counts) { if (cnt > 0) { candidates.push_back(val); } } // ヒープ操作のための比較関数 // make_heap / push_heap / pop_heap は max-heap を作る。 // top() に「最も早い要素(indexが最小)」を持ってきたい。 // したがって、「a が b より早い」なら「a > b (heap的に)」となるようにする。 // comp(a, b) が true なら a < b (heap的に)、つまり a は b より下に来る。 // 「a が b より遅い」ときに true を返せば、遅いものが下、早いものが上に来る。 auto comp = [&](int a, int b) { // a が b より「遅い(後に来る)」なら true を返す // is_before(b, a) が true なら b が先、つまり a が後 return is_before(b, a); }; // 初期ヒープの構築 make_heap(candidates.begin(), candidates.end(), comp); for (int i = 0; i < N; ++i) { // 先頭(最も早く現れる要素)を取り出す pop_heap(candidates.begin(), candidates.end(), comp); int best = candidates.back(); candidates.pop_back(); // 数列に追加 A.push_back(best); counts[best]--; // まだ残っていればヒープに戻す if (counts[best] > 0) { candidates.push_back(best); push_heap(candidates.begin(), candidates.end(), comp); } } // 結果出力 cout << "!"; for (int a : A) { cout << " " << a; } cout << endl; return 0; }