結果

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

ソースコード

diff # 

// gemini お試し 3
#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;
    
    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<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() {
    // 入出力の高速化（念のため）
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    if (!(cin >> N)) return 0;

    // --- フェーズ1: 楽観的な個数カウント ---
    vector<int> 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<int> 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<int> 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<int> 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<int> 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;
}
0