【Codeforces】1617D1 Too Many Impostors (easy version) 题解

题目大意

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

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

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

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

题目链接

思路

我们需要寻找一种可以确定两个玩家身份的方法，假设我们依次询问了 $(a, b, c)$、$(b, c, d)$，然后恰巧返回了不同的结果，那么就意味着 $a, d$ 的身份一定不同，因为两次询问中 $b, c$ 的身份不变，并且一定是一个 $1$、一个 $0$，否则两次询问结果不会不一样。

那么假如 $(a, b, c)$ 返回了 $1$，那么 $a$ 就是 crewmate，反之则为 impostor。

题目条件中的 $\frac{n}{3} < k < \frac{2n}{3}$ 保证了一定能在 $n$ 次内找到相邻询问结果不同的情况。

那么我们知道了一个 $0$、一个 $1$ 之后，就可以用他们依次询问其它的了，相当于每次询问 $1, 0, a_i$。

第一步需要花费 $n$ 次，即依次询问 $(1,2,3), (2,3,4), \ldots, (n-2,n-1,n), (n-1,n,1), (n,1,2)$。

第二步需要花费 $n-2$ 次，即确定其他的，所以总次数完全够用。

代码

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

const int maxN = 2e4 + 7;

int T, n, res[maxN];

int main()
{
    scanf("%d", &T);
    while(T--) {
        cin >> n;
        vector<int> imp;
        for(int i = 0; i < n; ++i) {
            cout << "? " << i + 1 << " " << (i+1) % n + 1 << " " << (i+2) % n + 1 << endl;
            cin >> res[i];
        }
        for(int i = 0; i < n; ++i) {
            if(res[i] != res[(i + 1) % n]) {
                if(res[i] == 0)
                    imp.push_back(i + 1);
                else
                    imp.push_back((i + 3) % n + 1);
                for(int j = 0; j < n; ++j) {
                    if(j != i && j != (i + 3) % n) {
                        cout << "? " << i + 1 << " " << (i+3) % n + 1 << " " << j + 1 << endl;
                        int pd;
                        cin >> pd;
                        if(pd == 0)
                            imp.push_back(j + 1);
                    }
                }
                break;
            }
        }
        cout << "! " << imp.size();
        for(int x : imp) cout << " " << x;
        cout << endl;
    }
    return 0;
}