【Codeforces】1617D2 Too Many Impostors (hard version) 题解

题目大意

此题为 hard 版本，与 easy 版本的差别在于可询问次数不一样，其余全一样。

交互题，有 $n$（$6 \le n \le 10^4$）个人，其中 $k$ 个为 impostors，$n-k$ 人为 crewmates，并且一定满足：

$$\frac{n}{3} < k < \frac{2n}{3}$$

可以进行至多 $n+6$ 次询问，每次询问时，输出 $a, b, c$，如果编号 $a, b, c$ 中 impostors 较多，则会返回 $0$，否则返回 $1$。

请在询问结束后，输出所有玩家的身份，crewmates 为 $0$，impostors 为 $1$。

题目链接

思路

建议先看一看 D1（简单版）的题解，弄懂之后就好理解这一篇题解了。

前一种方法在第一步中花费比较多（寻找一组 $0/1$），且询问的三人组结果在第二步中并没有进行使用，hard 版本就是要在这两点上进行优化。

step1：寻找一组 $imp, crew$

将玩家按三人组分组，查询 $(a_1,a_2,a_3), (a_4,a_5,a_6), \ldots$，记为 $triple[1], triple[4], \ldots$。

若 $triple[i] \ne triple[i+3]$，说明一组 $0$ 多、一组 $1$ 多，这 $6$ 人中一定存在相邻查询结果不同的边界。在这 $6$ 人内连续查询，就能找到一对 $0$ 和 $1$，分别记为 $imp, crew$（至多 $6$ 次额外查询）。

step2：确定其他人的身份

三个一组进行，每组只用 $2$ 次查询：

假设 $triple[i] = 0$（这一结果在第一步中已产生），意味着当前组 $0$ 多，则：

• 查询 $query(a_i, a_{i+1}, crew)$：
  • 若返回 $0$，说明前两个全是 $0$，单独查询第三个 $query(a_{i+2}, crew, imp)$；
  • 若返回 $1$，说明前两个一个 $1$ 一个 $0$（第三个是 $0$），再查 $query(a_i, crew, imp)$ 确定前两个的成分。（查成分是吧）

假设 $triple[i] = 1$，按照前面的思路反着来，查询 $query(a_i, a_{i+1}, imp)$。

不难发现，每组只用了 $2$ 次查询机会，总次数 $n/3 + 6 + 2n/3 = n + 6$ 刚好够用。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int maxN = 2e4 + 7;

int T, n, triple[maxN], role[maxN];

int query(int a, int b, int c)
{
    cout << "? " << a << ' ' << b << ' ' << c << endl;
    int r;
    cin >> r;
    return r;
}

int main()
{
    cin >> T;
    while(T--) {
        cin >> n;
        int imp, crew;
        memset(role, -1, sizeof role);
        for(int i = 1; i + 2 <= n; i += 3)
            triple[i] = query(i, i + 1, i + 2);
        for(int i = 1; i + 5 <= n; i += 3)
            if(triple[i] != triple[i + 3]) {
                for(int j = i + 1; j <= i + 2; ++j)
                    triple[j] = query(j, j + 1, j + 2);
                for(int j = i; j <= i + 2; ++j) {
                    if(triple[j] != triple[j + 1])
                        if(triple[j] ==0) {
                            role[j] = 0; role[j + 3] = 1;
                            imp = j; crew = j + 3;
                        }
                        else {
                            role[j] = 1; role[j + 3] = 0;
                            imp = j + 3; crew = j;
                        }
                    }
                break;
            }
        for(int i = 1; i + 2 <= n; i += 3) {
            if(i == imp || i + 1 == imp || i + 2 == imp || i == crew || i + 1 == crew || i + 2 == crew) {
                for(int j = i; j <= i + 2; ++j)
                    if(role[j] == -1)
                        role[j] = query(j, crew, imp);
            }
            else if(triple[i] == 0) {
                if(query(i, i + 1, crew) == 0) {
                    role[i] = role[i + 1] = 0;
                    role[i + 2] = query(i + 2, crew, imp);
                }
                else {
                    if(query(i, crew, imp) == 0) {
                        role[i] = 0; role[i + 1] = 1;
                    }
                    else {
                        role[i] = 1; role[i + 1] = 0;
                    }
                    role[i + 2] = 0;
                }
            }
            else {
                if(query(i, i + 1, imp) == 1) {
                    role[i] = role[i + 1] = 1;
                    role[i + 2] = query(i + 2, crew, imp);
                }
                else {
                    if(query(i, crew, imp) == 1) {
                        role[i] = 1; role[i + 1] = 0;
                    }
                    else {
                        role[i] = 0; role[i + 1] = 1;
                    }
                    role[i + 2] = 1;
                }
            }
        }
        cout << "! ";
        vector<int> ans;
        for(int i = 1; i <= n; ++i)
            if(role[i] == 0)
                ans.push_back(i);
        cout << ans.size();
        for(int i = 0; i < ans.size(); ++i)
            cout << ' ' << ans[i];
        cout << endl;
    }
}