[CF1491F] Magnets

Problem

你有 (n) 个磁铁，每个磁铁有属性，为下列三种之一

• N、S、-（表示无磁性）

一次操作你可以选择不相交的两个磁铁的子集 (S) 和 (T)，假设 (S) 中有 (n_1) 个 N，(s_1) 个 S， (T) 中有 (n_2) 个 N，(s_2) 个 S。这些你都不知道。通过交互库你可以得到 (n_1n_2-n_1s_2-n_2s_1+s_1s_2)（化简得到：((n_1-s_1)(n_2-s_2)) ）。得到的数值可能 (<0)。

你可以花费不超过 (n+lfloorlog_2n floor) 次操作找出所有没有磁性的磁铁。

多组数据 (Tleq 100)，每次 (nleq 2000)，(sum nleq 2000)。保证至少两个有磁极的磁铁和一个无磁极的磁铁。

Sol

如果我们能找到一个有磁极的磁铁，那么问题将非常简单。

然而要想找出一个有磁极的磁铁，必须借助另外至少一个有磁极的磁铁。

假象一种极端的边界：如果只有两块磁铁有磁极怎么办？只能硬着头皮一个一个找呗。

于是得到一种方案：每次查询 (S={i})，(T={1,cdots,i-1})。当遇到第二块有磁极的磁铁之前，答案一定为 (0)（因式有一项必为 (0)）。当 (i) 是第二块有磁极的磁铁时，答案会变成 (pm 1)，以此我们就能找出一块有磁极的磁铁了！

利用这块磁铁找出 (>i) 位置的无磁性的磁铁，这样总查询次数为 (n-1)。

但是第一块有磁性的磁铁我们还没有找到，如果找到了剩下的都是无磁性的磁铁。这时不必要一次一次找，观察题目使用技巧知道要二分找出来。于是继续构造 (S={i})，(T={1,cdots,j}) 来判断前缀 (j) 的磁铁中有没有有磁性的磁铁，然后二分，这部分查询次数为 (lceillog_2n ceil)。

综上，总次数 (=n-1+lceillog_2n ceilleq n+lfloorlog_2n floor)。时间复杂度为 (mathcal O(Tn^2))。

Code

#include <bits/stdc++.h>
using std::vector;
const int N = 2005;
int T, n, F;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 2; i <= n; i++) {
			printf("? 1 %d
%d
", i - 1, i);
			for (int j = 1; j < i; j++) printf("%d ", j);
			puts(""); fflush(stdout);
			scanf("%d", &F);
			if (F) {
				vector<int> ans;
				for (int j = i + 1; j <= n; j++) {
					printf("? 1 1
%d
%d
", i, j);
					fflush(stdout);
					scanf("%d", &F);
					if (!F) ans.push_back(j);
				}
				int l = 1, r = i - 1;
				while (l <= r) {
					int mid = l + r >> 1;
					printf("? 1 %d
%d
", mid, i);
					for (int j = 1; j <= mid; j++) printf("%d ", j);
					puts(""); fflush(stdout);
					scanf("%d", &F);
					if (F) r = mid - 1; else l = mid + 1;
				}
				for (int j = 1; j < i; j++)
					if (j != r + 1) ans.push_back(j);
				printf("! %d ", ans.size());
				for (int j = 0; j < ans.size(); j++) printf("%d ", ans[j]);
				puts(""); fflush(stdout); break;
			}
		}
	}
	return 0;
}