結果
| 問題 | No.3811 Mid Filter |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-21 02:41:25 |
| 言語 | C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 278 ms / 2,000 ms |
| + 999µs | |
| コード長 | 1,579 bytes |
| 記録 | |
| コンパイル時間 | 5,312 ms |
| コンパイル使用メモリ | 367,684 KB |
| 実行使用メモリ | 9,796 KB |
| 平均クエリ数 | 830.17 |
| 最終ジャッジ日時 | 2026-11-21 02:42:03 |
| 合計ジャッジ時間 | 10,130 ms |
|
ジャッジサーバーID (参考情報) |
judge1_0 / judge2_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 28 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
int ask(const vector<int>& q) {
cout << "?";
for (int x : q) cout << " " << x;
cout << endl;
int r;
cin >> r;
if (r == -1) exit(0);
return r;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
// 第一步:对前 2K+1 个数,每次扣掉 1 个问剩下的 2K 个
int m = 2 * k + 1;
vector<int> res(m + 1);
map<int, int> cnt;
for (int i = 1; i <= m; ++i) {
vector<int> q;
q.reserve(2 * k);
for (int j = 1; j <= m; ++j) {
if (j != i) q.push_back(j);
}
res[i] = ask(q);
cnt[res[i]]++;
}
int u = -1, vk1 = -1;
for (auto [val, c] : cnt) {
if (c == k + 1) u = val; // 出现 K+1 次的是第 K 小,即 max(L)
else vk1 = val; // 出现 K 次的是第 K+1 小
}
set<int> L;
vector<int> R;
for (int i = 1; i <= m; ++i) {
if (res[i] == vk1) L.insert(i);
else if ((int)R.size() < k - 1) R.push_back(i); // 任取 K-1 个大于 u 的垫背元素
}
// 第二步:逐个加入剩余元素,每次 1 次询问维护 L 和 u = max(L)
for (int x = m + 1; x <= n; ++x) {
vector<int> q(L.begin(), L.end());
q.insert(q.end(), R.begin(), R.end());
q.push_back(x);
int r = ask(q);
if (r != u) {
L.erase(u);
L.insert(x);
u = r;
}
}
cout << "!";
for (int x : L) cout << " " << x;
cout << endl;
}