Codeforces1617D1. Too Many Impostors (easy version)

传送门

题目大意

交互题， \(n(6\leq n<10^4,n\) 是 \(3\) 的倍数 \()\) 个人，其中有 \(k(\frac{n}{3} 个坏人， \(n-k\) 个好人。每次可以询问三个互不相同的人 \(a,b,c\) ，如果答案为 \(0\) ，说明他们三个中坏人多，答案为 \(1\) 则说明好人多，在 \(2n\) 次询问内求出 \(k\) 。

思路

可以从 \(1,2,3\) 开始询问，每次询问 \(x,x+1,x+2\) ，如果前后两次询问不同，则说明两次询问重叠部分的两个人 \(a,b\) 有一个是好人，一个是坏人，之后每次询问 \(a,b,x\) 可以得出其他所有人的身份，最后再找两个身份不同的人分别判断 \(a,b\) 的身份即可，最多会询问 \(2n\) 次。

代码

#include
#include
#include
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using PII = pair;
using TP = tuple;
#define all(x) x.begin(),x.end()
//#define int LL
//#define lc p*2
//#define rc p*2+1
//#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
//#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 1000000007;
const LL mod = 998244353;
const int maxn = 85;

int T, N;
vectorans;

void solve()
{
	int a, b, c, d;
	int t, lst = -1;
	for (int i = 3; i <= N; i++)
	{
		cout << "? " << i - 2 << ' ' << i - 1 << ' ' << i << endl;
		cin >> t;
		if (lst != -1 && lst != t)
		{
			a = i - 2, b = i - 1;
			break;
		}
		lst = t;
	}
	for (int i = 1; i <= N; i++)
	{
		if (i == a || i == b)
			continue;
		cout << "? " << a << ' ' << b << ' ' << i << endl;
		cin >> t;
		if (!t)
			ans.push_back(i), c = i;
		else
			d = i;
	}
	cout << "? " << c << ' ' << d << ' ' << a << endl;
	cin >> t;
	if (!t)
		ans.push_back(a);
	cout << "? " << c << ' ' << d << ' ' << b << endl;
	cin >> t;
	if (!t)
		ans.push_back(b);
	cout << "! " << ans.size() << ' ';
	for (auto& c : ans)
		cout << c << ' ';
	cout << endl;
}

int main()
{
	IOS;
	cin >> T;
	while (T--)
	{
		ans.clear();
		cin >> N;
		solve();
	}

	return 0;
}