結果

問題 No.3347 Guess The Array
コンテスト
ユーザー ponjuice
提出日時 2025-11-20 00:00:21
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,585 bytes
コンパイル時間 1,332 ms
コンパイル使用メモリ 118,228 KB
実行使用メモリ 26,368 KB
平均クエリ数 3704.46
最終ジャッジ日時 2025-11-20 00:00:37
合計ジャッジ時間 15,017 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 37 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using namespace std;

// グローバル変数
int N;
vector<int> A_fixed; // 確定済みの数列
map<int, int> counts; // 各数字の「残り」出現回数

// クエリ送信
bool ask(const vector<int>& 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<int> 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<int> 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<int> q(mid, v);
            if (ask(q)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        counts[v] = ans;
    }

    // 2. 候補リストの作成（順序付き）
    // 常に「出現順」にソートされた状態を保つ
    vector<int> 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;
}
0