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;
}