// gemini お試し 2 #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; // flush string res; cin >> res; return res == "Yes"; } // u が v より「先」に来るか判定する // 前提: u, v は共に残り回数が 1 以上であり、u != v bool is_before(int u, int v) { // クエリ B = (確定済みprefix) + (u) + (v を残り全個数) // もし u が先なら、最初の u をマッチした後、残りの v がすべてマッチする (Yes) // もし v が先なら、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() { // 入力 if (!(cin >> N)) return 0; // 1. 各数字の出現回数を特定する // 線形探索だと遅いので、指数探索 + 二分探索を行う for (int v = 1; v <= N; ++v) { // まず1個あるか確認 if (!ask({v})) { counts[v] = 0; continue; } // 指数探索で範囲を絞る int count = 1; while (true) { int next_count = count * 2; // Nを超える長さは聞く必要がない(というか聞けない) if (next_count > N) { // 範囲は [count, N] break; } vector q(next_count, v); if (ask(q)) { count = next_count; } else { // 範囲は [count, next_count - 1] break; } } // 二分探索で確定させる // 範囲 [low, high] で、low は存在確認済み int low = count; int high = min(N, count * 2); // count*2 までは可能性あり、ただしN以下 // high が実際に存在するかはまだ不明な場合があるため、通常の二分探索を行う // 最大の k を探す int ans = low; while (low <= high) { int mid = low + (high - low) / 2; if (mid == 0) { low = 1; continue; } // basic guard // mid個について問い合わせ(lowと同じなら聞く必要なし) if (mid == ans) { low = mid + 1; continue; } vector q(mid, v); if (ask(q)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } counts[v] = ans; } // 2. 候補リストの作成(順序付き) // 常に「出現順」にソートされた状態を保つ vector candidates; // 比較関数: a が b より先なら true auto comp = [&](int a, int b) { return is_before(a, b); }; // 初期候補(個数が1以上のもの)をリストに追加 for (auto const& [val, cnt] : counts) { if (cnt > 0) { // 二分探索で挿入位置を探す (lower_bound) // lower_bound は「comp(element, val) が false になる最初の位置」を返す // つまり「element が val より先」ではない最初の位置 auto it = lower_bound(candidates.begin(), candidates.end(), val, comp); candidates.insert(it, val); } } // 3. 数列の復元 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) { // 比較回数を log(current_size) に抑える 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; }