【JOISC 2020】Chameleon’s Love
题目
题目译自 JOISC 2020 Day2 T1「カメレオンの恋 / Chameleon’s Love」
注意：在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：
C++
C++ 11
C++ 17
C++ (NOI)
C++ 11 (NOI)
C++ 11 (Clang)
C++ 17 (Clang)
在 JOI 动物园中，有着 只变色龙，编号为 。其中，有 只变色龙的性别为 X，其余 只的性别为 Y。
每只变色龙都有一个原色。关于原色的可公开情报如下：
所有性别为 X 的变色龙的原色不同。
对于每只性别为 X 的变色龙，都存在唯一的原色与其相同的变色龙，且性别为 Y。
现在，JOI 动物园迎来了恋爱的季节。每只变色龙都爱上了另一只变色龙。关于恋爱对象的可公开情报如下：
每只变色龙都很专一于唯一一只异性的变色龙。
一只变色龙和它的恋爱对象的原色不同。
不存在两只变色龙同时追求另一只变色龙。
你可以召集一部分变色龙来组织一场会议。对于一只参加会议的变色龙 ，令 为它的恋爱对象。 的肤色由以下方式决定：
如果 参加了这场会议，则 的肤色为 的原色。
如果 没参加这场会议，则 的肤色为 的原色。
一只变色龙的肤色可以在不同的会议间发生改变。对于你组织的一场会议，你可以得到场上所有变色龙的肤色的种类数。
由于变色龙也会感到厌烦，所以你最多只能组织 场会议。同时你需要根据你得到的信息，确定有哪些变色龙的原色相同。
请你写一个程序在组织不超过 场会议的前提下确定所有相同原色的变色龙。
实现细节
你需要提交一个文件。
这个文件的名字应为 。这个程序应当包含 ，且其中需要实现以下函数：
对于每组测试数据，保证这个函数会被恰好调用一次。
其参数 为题目中的 ，性别为 X 的变色龙的个数。
你的程序可以调用以下函数：
你可以通过调用这个函数组织一场会议。
参数 是参加这场会议的变色龙的列表。
返回值即为本场会议所有变色龙的肤色的种类数。
中的每个元素都应该是一个 内的整数，否则你的程序将会被判为 Wrong Answer [1]。
中的元素不得重复，否则你的程序将会被判为 Wrong Answer [2]。
你的程序不应调用 函数超过 次，否则你的程序将会被判为 Wrong Answer [3]。
你可以通过调用这个函数回答一对原色相同的变色龙。
参数 和 表示变色龙 的原色相同。
必须保证 ，否则你的程序将会被判为 Wrong Answer [4]。
你的程序不得以相同的 值或 值调用此函数两次及以上，否则你的程序将会被判为 Wrong Answer [5]。
如果 的原色不同，你的程序将会被判为 Wrong Answer [6]。
你的程序应当调用 函数恰好 次，否则你的程序将会被判为 Wrong Answer [7]。
实现提示
你的程序可以实现其他函数供内部使用，或使用全局变量。
你的程序不得访问标准输入输出流，也不得通过任何方法访问其他文件。不过，你的程序可以输出到标准错误流。
编译与运行
你可以在附加文件中下载到一个压缩文件，其中包含一个样例交互库以测试你的程序。这个压缩文件也包含了一个你应当提交的程序的样例。
样例交互库为 。为了测试你的程序，请把 放在同一目录下，并执行以下命令来编译你的程序：
若编译成功，会在当前目录生成一个可执行文件 。
请注意样例交互库并非实际交互库。样例交互库仅是由一个单一的，从标准输入流读入数据，并将结果输出到标准输出流的过程构成的。
输入格式
样例交互库从标准输入流读入以下数据：
第一行，一个整数 。
第二行， 个整数 ，表示每只变色龙的性别，若其为 则性别为 X，否则为 Y。
第三行， 个整数 ，表示每只变色龙的原色，保证其在 内。
第四行， 个整数 ，表示每只变色龙的恋爱对象。
输出格式
样例交互库向标准输入流输出以下数据：
若你的程序是正确的，样例交互库将以 的形式输出你调用 的次数。
若你的程序被判为 Wrong Answer，样例交互库将以 的形式输出其类型。
若你的程序触发了不止一种 Wrong Answer，样例交互库只会输出其中一种。
样例
样例输入 1
4
1 0 1 0 0 1 1 0
4 4 1 2 1 2 3 3
4 3 8 7 6 5 2 1
样例调用
调用 子调用 返回值
在附加文件中， 满足第一个子任务的限制， 满足第四个子任务的限制。
数据范围与提示
对于所有数据，满足：
。
。
。
对于每个 ，存在一个唯一的 满足 。
对于每个 ，存在一个唯一的 满足 。
。
。
。
。
详细子任务附加条件及分值如下表：
子任务编号 附加限制 分值
显示分类标签
思路
首先考虑n^2怎么做
我们两两做一次询问，答案为1的就连一条边（这代表他们要么同色，要么是单恋）
可以发现，点的度数要么为1，要么为3，分类讨论一下即可
然后看左边为X右边为Y的
很显然，最后的图是一个二分图，X一边，Y一边。
我们考虑前n个（都是X），对于每一个，用二分的方式查找它的连边即可
考虑原题
受到刚才的启发，我们会想到把XY分开，可是我想不到怎么分……
demo，我们有更巧的方法：我们只要分开之后满足是二分图就可以二分找边了
开两个队列，如果一个元素与队列1有连边，那么进入队列2，否则进入队列1，这样只有队列之间有连边
然后我们把队列2再做处理，处理到没有元素为止，就做完啦
代码
#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> V;
const int N = 1005;
V e[N];
int v[2][N], vc[2], i, j, x, col[N], n;
void dfs(int x, int c) {
col[x] = c;
for (int y : e[x])
if (col[y] == -1)
dfs(y, c ^ 1);
}
inline void getcol() {
memset(col + 1, -1, n << 2);
for (j = 1; j < i; ++j)
if (col[j] == -1)
dfs(j,0);
memset(vc, 0, 8);
for (j = 1; j < i; ++j) v[col[j]][++vc[col[j]]] = j;
}
bool b[N];
int a[N], xb;
bool ck(int o, int l, int r) {
a[xb = 1] = i;
for (j = l; j <= r; ++j)
if (!b[v[o][j]])
a[++xb] = v[o][j];
return Query(V(a + 1, a + xb + 1)) < xb;
}
int ask(int o, int l, int r) {
if (l == r)
return v[o][l];
int m = l + r >> 1;
return ck(o, l, m) ? ask(o, l, m) : ask(o, m + 1, r);
}
void solve(int nn) {
n = nn * 2;
for (i = 1; i <= n; ++i) {
cerr << i << endl;
if (i == 7)
++i, --i;
getcol();
memset(b + 1, 0, n);
for (int o = 0; o < 2; ++o)
for (; ck(o, 1, vc[o]);) x = ask(o, 1, vc[o]), e[i].push_back(x), e[x].push_back(i), b[x] = 1;
}
srand(114514);
static int too[N];
for (i = 1; i <= n; ++i)
if (e[i].size() == 3) {
random_shuffle(e[i].begin(), e[i].end());
for (j = 0; j < 3; ++j) {
V v = { i };
for (int k = 0; k < 3; ++k)
if (j != k)
v.push_back(e[i][k]);
if (Query(v) == 1) {
too[i] = e[i][j];
break;
}
}
}
for (i = 1; i <= n; ++i)
if (too[i]) {
e[i].erase(find(e[i].begin(), e[i].end(), too[i]));
e[too[i]].erase(find(e[too[i]].begin(), e[too[i]].end(), i));
}
for (i = 1; i <= n; ++i) assert(e[i].size() == 1);
for (i = 1; i <= n; ++i)
if (i < e[i][0])
Answer(i, e[i][0]);
}
void Solve(int n) { solve(n); }