CF1147E Rainbow Coins 题解

题意：

cxy 有 $n$ 枚各种颜色的硬币，她想把它们分类成堆。这些硬币标号为 $1, 2, \ldots, n$，每个硬币是红色、绿色或蓝色之一。她希望将硬币分类成三堆，其中一堆包含所有的红色硬币，一堆包含所有的绿色硬币，另一堆包含所有的蓝色硬币。

不幸的是，~~cxy 是色盲~~，因此她无法完成这项任务。幸运的是，她有一个朋友可以检查一对硬币并告诉 cxy 它们是否是同一种颜色。利用她的朋友，cxy 相信她现在可以对硬币进行分类。

堆之间的顺序无所谓，只要相同颜色的硬币在同一堆里，不同颜色的硬币不在同一堆里即可。

她的朋友会批量回答关于多个硬币对的问题，并且会并行回答这些对的所有问题。每个批次中，每个硬币最多只能出现在一个对中。同一个硬币可以出现在不同的批次中。

cxy 只能使用 $7$ 次询问。帮她找到分类后的硬币堆。

交互格式：

会给出多个测试用例。第一行包含一个整数 $t$ $(1 \leq t \leq 5)$——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ $(1 \leq n \leq 10^5)$——硬币的数量。

如果要询问，请输出 “Q $k\ x_1\ y_1\ \ldots\ x_k\ y_k$” $(1 \leq k \leq \frac{n}{2}, 1 \leq x_i, y_i \leq n, x_i \neq y_i)$。$k$ 表示批次中的对数，$x_i, y_i$ 表示第 $i$ 对硬币的编号。在一个批次中，每个硬币只能出现一次。所有 $x_i$ 和 $y_i$ 应该是不同的。

评测姬将回应一个长度为 $k$ 的 01 串，其中第 $i$ 个字符为 “1” 表示 $x_i$ 和 $y_i$ 是同一种颜色，否则为 “0”。

如果你给出了一个无效的查询，评测姬会回应 $-1$。请确保立即退出以避免获得其他评测结果。

当你准备回答时，输出四行。

第一行包含 “A $k_1\ k_2\ k_3$” $(0 \leq k_1, k_2, k_3$ 且 $k_1 + k_2 + k_3 = n$)。这些表示三堆的大小。

第二行包含 $k_1$ 个整数，表示第一堆硬币的编号。

第三行包含 $k_2$ 个整数，表示第二堆硬币的编号。

第四行包含 $k_3$ 个整数，表示第三堆硬币的编号。

每个硬币必须恰好出现在一堆中。你每个测试用例最多可以询问 $7$ 次。

考虑前两次询问：

$(1,2),(3,4),\cdots,(2k-1,2k)$
$(2,3),(4,5),\cdots,(2k,2k+1)$

这样我们就可以知道相邻的两个位置颜色是否相同，如果相同就将它们合并。

设现在的每个数为 $a_i$ 满足 $a_{i-1},a_{i}$ 颜色不同且 $a_i,a_{i+1}$ 颜色不同。

现在我们要知道 $a_{i-1}$ 和 $a_{i+1}$ 的颜色区别。

考虑处理每个 $a_{i-1},a_i,a_{i+1}$ 的结构再将他们的结果合并，即询问：

$(a_{i-2},a_i)$ ，对于 $i=3,4,7,8,11,12,14,15,\cdots$

即 $i$ 为奇数时询问 $(1,3),(5,7),\cdots$ ，$i$ 为偶数时询问 $(2,4),(6,8),\cdots$
$(a_{i}, a_{i+2})$ ，对于 $i=3,4,7,8,11,12,14,15,\cdots$

即 $i$ 为奇数时询问 $(3,5),(7,9),\cdots$ ，$i$ 为偶数时询问 $(4,6),(8,10),\cdots$

这样我们就知道所有点的颜色了。

时间复杂度 $\mathcal{O}(n)$ ，询问次数为 $4$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
typedef pair<int,int> pii;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define repc(i, a, b, c) for(int i = (a), i##END = (b); i <= i##END; i += (c))
#define Fi first
#define Se second
#define pb push_back
#define N ((int)(1e5 + 15))

int now[N], ans[N];
char s[N]; vector<int> A, B, C; map<pii, bool> col;
void ask()
{
    if(!A.size()) return;
    cout << "Q " << A.size() << ' ';
    rep(i, 0, A.size() - 1) cout << A[i] << ' ' << B[i] << ' ';
    cout << endl; cin >> s; rep(i, 0, A.size() -  1) col[{A[i], B[i]}] = (s[i] == '1');
}
void clear(int n) { col.clear(); rep(i, 0, n) ans[i] = 0; A.clear(); B.clear(); C.clear(); }
void solve()
{
    int n, cnt = 0; cin >> n; clear(n + 5); 
    repc(i, 2, n, 2) { A.pb(i - 1); B.pb(i); } ask(); A.clear(); B.clear();
    repc(i, 3, n, 2) { A.pb(i - 1); B.pb(i); } ask(); A.clear(); B.clear();
    now[++cnt] = 1; rep(i, 2, n) if(!col[{i - 1, i}]) now[++cnt] = i;
    repc(i, 3, cnt, 4) { A.pb(now[i - 2]); B.pb(now[i]); }
    repc(i, 4, cnt, 4) { A.pb(now[i - 2]); B.pb(now[i]); } ask(); A.clear(); B.clear();
    repc(i, 3, cnt - 2, 4) { A.pb(now[i]); B.pb(now[i + 2]); }
    repc(i, 4, cnt - 2, 4) { A.pb(now[i]); B.pb(now[i + 2]); } ask(); A.clear(); B.clear();
    ans[now[1]] = 1; if(cnt > 1) ans[now[2]] = 2;
    rep(i, 3, cnt)
    {
        if(col[{now[i - 2], now[i]}]) ans[now[i]] = ans[now[i - 2]];
        else ans[now[i]] = 6 - ans[now[i - 2]] - ans[now[i - 1]];
    }
    for(int i = 1, t = 0; i <= n; i++)
    {
        if(ans[i]) { t = ans[i]; } ans[i] = t;
        if(ans[i] == 1) A.pb(i);
        else if(ans[i] == 2) B.pb(i);
        else if(ans[i] == 3) C.pb(i);
    }
    cout << "A " << A.size() << ' ' << B.size() << ' ' << C.size() << '\n';
    for(auto i : A) { cout << i << ' '; } cout << '\n';
    for(auto i : B) { cout << i << ' '; } cout << '\n';
    for(auto i : C) { cout << i << ' '; } cout << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}