結果

問題 No.3811 Mid Filter
コンテスト
ユーザー sepa38
提出日時 2026-11-13 12:17:09
言語 C++23(gnu拡張gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc16.so -lm -std=gnu++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,245 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,039 ms
コンパイル使用メモリ 371,308 KB
実行使用メモリ 9,900 KB
平均クエリ数 830.17
最終ジャッジ日時 2026-11-20 20:53:08
合計ジャッジ時間 10,584 ms
ジャッジサーバーID
(参考情報)
judge1_0 / judge2_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 12 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

// 誤解法2: 「答えが y なら y は下位 K に入る」と判定
//   y < max(L) でも、L∪{y} の 2 番目に大きいのが y とは限らない (y が L の 2 番目以下のとき
//   答えは L の別の要素)。そのケースを「入らない」と誤判定する。
#include <bits/stdc++.h>
using namespace std;

int N, K;

int ask(const vector<int>& s) {
    string out = "?";
    for (int x : s) { out += ' '; out += to_string(x); }
    out += '\n';
    fputs(out.c_str(), stdout);
    fflush(stdout);
    int r;
    if (scanf("%d", &r) != 1 || r == -1) exit(0);
    return r;
}

int main() {
    scanf("%d %d", &N, &K);
    const int M = 2 * K + 1;

    // Phase 1: S = {1..2K+1} から i を抜いて質問
    //   S の昇順を c_1 < ... < c_{2K+1} とすると
    //   rank(i) <= K   なら 答えは c_{K+1}  (K 回現れる)
    //   rank(i) >= K+1 なら 答えは c_K      (K+1 回現れる)
    vector<int> res(M + 1);
    for (int i = 1; i <= M; i++) {
        vector<int> s;
        for (int j = 1; j <= M; j++) if (j != i) s.push_back(j);
        res[i] = ask(s);
    }
    map<int, int> cnt;
    for (int i = 1; i <= M; i++) cnt[res[i]]++;
    int p = -1, q = -1;  // p = c_{K+1} の添字, q = c_K の添字
    for (auto [v, c] : cnt) (c == K ? p : q) = v;

    vector<int> L, H;  // L: 現在の下位 K 個, H: L の全要素より大きいと分かっている要素
    for (int i = 1; i <= M; i++) (res[i] == p ? L : H).push_back(i);
    int mx = q;  // L の最大要素の添字

    // Phase 2: L ∪ {y} ∪ (H の K-1 個) を質問
    //   y > max(L) なら 答えは max(L)
    //   y < max(L) なら 答えは L∪{y} の 2 番目に大きい要素 = 新しい max(L)
    for (int y = M + 1; y <= N; y++) {
        vector<int> s = L;
        s.push_back(y);
        for (int i = 0; i < K - 1; i++) s.push_back(H[i]);
        int r = ask(s);
        if (r == y) {  // BUG: 正しくは r != mx
            L.erase(find(L.begin(), L.end(), mx));
            L.push_back(y);
            H.push_back(mx);
            mx = r;
        }
    }

    string out = "!";
    for (int x : L) { out += ' '; out += to_string(x); }
    out += '\n';
    fputs(out.c_str(), stdout);
    fflush(stdout);
}
0