結果

問題 No.3347 Guess The Array
コンテスト
ユーザー ponjuice
提出日時 2025-11-19 23:54:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,662 bytes
コンパイル時間 1,565 ms
コンパイル使用メモリ 117,788 KB
実行使用メモリ 26,540 KB
平均クエリ数 4342.52
最終ジャッジ日時 2025-11-19 23:54:24
合計ジャッジ時間 21,635 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

// gemini お試し
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

// グローバル変数として保持
int N;
vector<int> A; // 現在確定している数列
map<int, int> counts; // 各数字の残りの出現回数

// クエリを投げる関数
bool ask(const vector<int>& 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<int> 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<int> q(current_cnt + 1, v);
            if (ask(q)) {
                current_cnt++;
            } else {
                break;
            }
        }
        counts[v] = current_cnt;
    }

    // フェーズ2: 順序の決定
    // 候補となる数字（count > 0）を管理する
    vector<int> 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;
}
0