結果
| 問題 | No.3811 Mid Filter |
| コンテスト | |
| ユーザー |
sepa38
|
| 提出日時 | 2026-11-13 12:17:09 |
| 言語 | C++23(gnu拡張gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 2,245 bytes |
| 記録 | |
| コンパイル時間 | 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 |
ソースコード
// 誤解法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);
}
sepa38