UOJ Logo Universal Online Judge

UOJ

#504. 【JOISC2020】变色龙

附件下载 统计

在JOI动物园里有 $2N$ 只变色龙,从 $1$ 到 $2N$ 编号。在它们中有 $N$ 只变色龙的性别是 X,另外 $N$ 只的性别是Y。

每个变色龙都有自己的原色。变色龙的原色具有以下性质:

  • 同性变色龙的原色是两两不同的。
  • 每只变色龙都有一只原色相同的异性变色龙。

现在,JOI动物园到了爱情的季节。每只变色龙都另一只变色龙。变色龙的爱具有以下性质:

  • 每只变色龙恰好爱一只异性变色龙。
  • 每只变色龙爱的变色龙和它自己原色不同。
  • 所有变色龙爱的变色龙两两不同。

你可以聚集一些变色龙组织一场见面会。对每只参加见面会的变色龙$s$,记它爱的变色龙为$t$,$s$的颜色由以下规则决定:

  • 如果$t$也参加了见面会,$s$的颜色是$t$的原色。
  • 否则, $s$的颜色是$s$的原色。

变色龙的颜色在不同的见面会中可能不保持一致。对于每场见面会,你可以数出参加的变色龙有多少不同的颜色。

你想通过举行至多$20000$场见面会来确定每对有着相同原色的变色龙。

实现细节

你的程序需要包含chameleon.h

  • 要实现函数void Solve(int N)

这个函数在每个测试点中会被调用恰好一次。$N$表示具有每种性别的变色龙的数量。(也就是说,一共有$2N$只变色龙。)

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

  1. `int Query(const std::vector &p)

你可以通过调用这个函数来举行一场见面会。

  • $p$是来参加见面会的变色龙的编号列表。
  • 返回值是来参加见面会的变色龙的颜色种数。
  • 每个$p$中的元素都应不小于$1$,不大于$2N$。否则你的程序将被判为Wrong Answer [1]
  • $p$中的元素应两两不同。否则你的程序将被判为Wrong Answer [2]
  • 你的程序不能调用这个函数超过$20000$次。否则你的程序将被判为Wrong Answer [3]

  • void Answer(int a, int b)

你可以通过这个函数来报告一对具有相同原色的变色龙。

  • 参数$a,b$表示变色龙$a,b$具有相同的原色。
  • 必须保证$1 \leq a,b \leq 2N$。否则你的程序将被判为Wrong Answer [4]
  • 不能对同一对$a,b$调用超过一次这个函数。否则你的程序将被判为Wrong Answer [5]
  • 如果变色龙$a$和$b$的原色不同,你的程序将被判为Wrong Answer [6]
  • 你的程序应该恰好调用这个函数$N$次。否则你的程序将被判为Wrong Answer [7]

重要提示

  • 你的程序可以定义全局变量或其他函数。
  • 你的程序不需要也不应该访问标准输入输出,也不应该访问任何文件。

本机测试的方法

grader.cppchameleon.cppchameleon.h放在当前目录下,运行

g++ -std=gnu++14 -O2 -o grader grader.cpp chameleon.cpp

当编译成功时,文件grader将被生成。

样例交互库的输入格式

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

$N$

$Y_1 \cdots Y_{2N}$

$C_1 \cdots C_{2N}$

$L_1 \cdots L_{2N}$

$Y_i$表示第$i$只变色龙的性别,取值范围是${0,1}$,分别表示性别X和Y。

$C_i$表示第$i$只变色龙的原色,取值范围是$[1,N]$中的整数。

$L_i$表示第$i$只变色龙爱的变色龙的编号。

样例交互库的输出格式

当你的程序顺利结束时,样例交互库将向标准输出写入以下内容:

  • 如果你的程序运行结果正确,将输出你的程序调用Query的次数。比如Acepted: 100
  • 如果你的程序答案错误,将输出错误类型。比如Wrong Answer [1]

如果你的程序同时触发了多种类型的错误,交互库只会报告其中的一种。

限制与约定

  • $2 \leq N \leq 500$
  • $0 \leq Y_i \leq 1 (1 \leq i \leq 2N)$
  • $1 \leq C_i \leq N (1 \leq i \leq 2N)$
  • 对任意$j(1 \leq j \leq N)$,有且仅有一个$i(1 \leq i \leq 2N)$使$Y_i=0,C_i=j$
  • 对任意$j(1 \leq j \leq N)$,有且仅有一个$i(1 \leq i \leq 2N)$使$Y_i=1,C_i=j$
  • $1 \leq L_i \leq 2N(1 \leq i \leq 2N)$
  • $Y_i \neq Y_{L_i} (1 \leq i \leq 2N)$
  • $C_i \neq C_{L_i} (1 \leq i \leq 2N)$
  • $L_k \neq L_l (1 \leq k < l \leq 2N)$

子任务

  1. (4 分) $L_{L_i} = i(1 \leq i \leq 2N)$
  2. (20 分) $N \leq 7$
  3. (20 分) $N \leq 50$
  4. (20 分) $Y_i=0(1 \leq i \leq N)$
  5. (36 分) 没有特殊限制

样例交互过程

样例交互过程

下载

样例及测评库下载