#16053. 「JOISC 2020 Day2」变色龙之恋

内存限制:512 MiB 时间限制:2000 ms 题目类型:交互
上传者: Woshiluo

题目描述

题目译自 JOISC 2020 Day2 T1「カメレオンの恋 / Chameleon’s Love

注意:在 LibreOJ 上,由于语言限制,目前只支持以下语言的提交:

  • C++ 11
  • C++ 17
  • C++ 11 (NOI)
  • C++ 11 (Clang)
  • C++ 17 (Clang)

在 JOI 动物园中,有着 2N 只变色龙,编号为 1\ldots 2N 。其中,有 N 只变色龙的性别为 X,其余 N 只的性别为 Y。

每只变色龙都有一个原色。关于原色的可公开情报如下:

  • 所有性别为 X 的变色龙的原色不同。
  • 对于每只性别为 X 的变色龙,都存在唯一的原色与其相同的变色龙,且性别为 Y。

现在,JOI 动物园迎来了恋爱的季节。每只变色龙都爱上了另一只变色龙。关于恋爱对象的可公开情报如下:

  • 每只变色龙都很专一于唯一一只异性的变色龙。
  • 一只变色龙和它的恋爱对象的原色不同。
  • 不存在两只变色龙同时追求另一只变色龙。

你可以召集一部分变色龙来组织一场会议。对于一只参加会议的变色龙 s ,令 t 为它的恋爱对象。 s 肤色由以下方式决定:

  • 如果 t 参加了这场会议,则 s 的肤色为 t 的原色。
  • 如果 t 没参加这场会议,则 s 的肤色为 s 的原色。

一只变色龙的肤色可以在不同的会议间发生改变。对于你组织的一场会议,你可以得到场上所有变色龙的肤色的种类数。

由于变色龙也会感到厌烦,所以你最多只能组织 20\,000 场会议。同时你需要根据你得到的信息,确定有哪些变色龙的原色相同。
请你写一个程序在组织不超过 20\,000 场会议的前提下确定所有相同原色的变色龙。

实现细节

你需要提交一个文件。
这个文件的名字应为 \texttt{chameleon.cpp} 。这个程序应当包含 \texttt{chameleon.h} ,且其中需要实现以下函数:

  • \texttt{void Solve(int N)}
    对于每组测试数据,保证这个函数会被恰好调用一次。
    • 其参数 \texttt N 为题目中的 N ,性别为 X 的变色龙的个数。

你的程序可以调用以下函数:

  • \texttt{int Query(const std::vector<int> &p)}
    你可以通过调用这个函数组织一场会议。
    • 参数 \texttt p 是参加这场会议的变色龙的列表。
    • 返回值即为本场会议所有变色龙的肤色的种类数。
    • \texttt p 中的每个元素都应该是一个 [1,2N] 内的整数,否则你的程序将会被判为 Wrong Answer [1]
    • \texttt p 中的元素不得重复,否则你的程序将会被判为 Wrong Answer [2]
    • 你的程序不应调用 \texttt{Query} 函数超过 20\,000 次,否则你的程序将会被判为 Wrong Answer [3]
  • \texttt{void Answer(int a, int b)}
    你可以通过调用这个函数回答一对原色相同的变色龙。
    • 参数 \texttt a \texttt b 表示变色龙 a,b 的原色相同。
    • 必须保证 1 \le a,b \le 2N ,否则你的程序将会被判为 Wrong Answer [4]
    • 你的程序不得以相同的 a 值或 b 值调用此函数两次及以上,否则你的程序将会被判为 Wrong Answer [5]
    • 如果 a,b 的原色不同,你的程序将会被判为 Wrong Answer [6]
    • 你的程序应当调用 \texttt{Answer} 函数恰好 N 次,否则你的程序将会被判为 Wrong Answer [7]

实现提示

  • 你的程序可以实现其他函数供内部使用,或使用全局变量。
  • 你的程序不得访问标准输入输出流,也不得通过任何方法访问其他文件。不过,你的程序可以输出到标准错误流。

编译与运行

你可以在附加文件中下载到一个压缩文件,其中包含一个样例交互库以测试你的程序。这个压缩文件也包含了一个你应当提交的程序的样例。
样例交互库为 \texttt{grader.cpp} 。为了测试你的程序,请把 \texttt{grader.cpp},\texttt{chameleon.h},\texttt{chameleon.cpp} 放在同一目录下,并执行以下命令来编译你的程序:

\texttt{g++ -std=gnu++14 -O2 -o grader grader.cpp chameleon.cpp}

若编译成功,会在当前目录生成一个可执行文件 \texttt{grader}
请注意样例交互库并非实际交互库。样例交互库仅是由一个单一的,从标准输入流读入数据,并将结果输出到标准输出流的过程构成的。

输入格式

样例交互库从标准输入流读入以下数据:

第一行,一个整数 N
第二行, 2N 个整数 Y_i ,表示每只变色龙的性别,若其为 0 则性别为 X,否则为 Y。
第三行, 2N 个整数 C_i ,表示每只变色龙的原色,保证其在 [1,N] 内。
第四行, 2N 个整数 L_i ,表示每只变色龙的恋爱对象。

输出格式

样例交互库向标准输入流输出以下数据:

  • 若你的程序是正确的,样例交互库将以 \texttt{Accepted: 100} 的形式输出你调用 \texttt{Query} 的次数。
  • 若你的程序被判为 Wrong Answer,样例交互库将以 \texttt{Wrong Answer [1]} 的形式输出其类型。

若你的程序触发了不止一种 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

样例调用

调用 子调用 返回值
\texttt{Solve(4)}
\texttt{Query([])} \texttt0
\texttt{Query([6, 2])} \texttt2
\texttt{Query([8, 1, 6])} \texttt2
\texttt{Query([7, 1, 3, 5, 6, 8])} \texttt4
\texttt{Query([8, 6, 4, 1, 5])} \texttt3
\texttt{Answer(6, 4)}
\texttt{Answer(7, 8)}
\texttt{Answer(2, 1)}
\texttt{Answer(3, 5)}

在附加文件中, \texttt{sample-02.txt} 满足第一个子任务的限制, \texttt{sample-03.txt} 满足第四个子任务的限制。

数据范围与提示

对于所有数据,满足:

  • 2 \le N \le 500
  • 0 \le Y_i \le 1\ (1 \le i \le 2N)
  • 1 \le C_i \le N\ (1 \le i \le 2N)
  • 对于每个 j\ (1 \le j \le N) ,存在一个唯一的 i\ (1 \le i \le 2N) 满足 Y_i = 0, C_i = j
  • 对于每个 j\ (1 \le j \le N) ,存在一个唯一的 i\ (1 \le i \le 2N) 满足 Y_i = 1, C_i = j
  • 1 \le L_i \le 2N\ (1 \le i \le 2N)
  • Y_i \ne Y_{L_i}\ (1 \le i \le 2N)
  • C_i \ne C_{L_i}\ (1 \le i \le 2N)
  • L_k \ne L_l\ (1 \le k < l \le 2N)

详细子任务附加条件及分值如下表:

子任务编号 附加限制 分值
1 L_{L_i}=i\ (1 \le i \le 2N) 4
2 N \le 7 20
3 N \le 50 20
4 Y_i = 0\ (1 \le i \le N) 20
5 - 36