有 $2N$ 张卡片,每张卡片正面写有一个 $0$ 到 $N-1$ 之间的整数,且每个整数恰好出现两次。你和 JOI 君正在练习一种名为“神经衰弱”的游戏。
游戏开始时,卡片背面朝上在桌面上排成一列。我们将从左起第 $i+1$ 张卡片($0 \le i \le 2N-1$)称为卡片 $i$。设卡片 $i$ 正面写的整数为 $A_i$($0 \le i \le 2N-1$)。起初,你和 JOI 君都不知道 $A_i$ 的具体值。
你和 JOI 君可以进行最多 $K$ 次以下交互:
- 你指定 $2N$ 张卡片中的 $2$ 张。
- JOI 君翻开这两张卡片,在不让你看到的情况下偷偷查看它们正面写的整数。如果两张卡片上的整数相同,他会记住该值并告诉你。否则,他会从这两张卡片上的整数中选出一个他认为“更容易记住”的整数,记住它并告诉你。
JOI 君对整数的“易记程度”由 $N$ 个整数 $P_0, P_1, \dots, P_{N-1}$ 表示。这些整数满足以下两个条件: $0 \le P_i \le N-1$($0 \le i \le N-1$)。 $P_i \neq P_j$($0 \le i < j \le N-1$)。
对于 JOI 君而言,整数 $i$ 比整数 $j$ 更容易记住,等价于 $P_i < P_j$ 成立。
你的任务是通过与 JOI 君进行不超过 $K$ 次交互,确定每张卡片上写的整数。注意,你并不知道表示 JOI 君易记程度的整数 $P_0, P_1, \dots, P_{N-1}$ 的具体值。
实现细节
你需要编写一个程序,实现确定每张卡片上所写整数的方法。程序必须包含 Memory2_lib.h。
程序必须实现以下函数:
void Solve(int T, int N)
该函数对每个测试用例仅调用一次。参数 $T$ 表示子任务编号,$N$ 表示共有 $2N$ 张卡片。
该函数必须通过调用 Flip 来确定卡片上写的整数,并通过调用 Answer 来回答结果。
程序中可以调用以下函数:
int Flip(int I, int J)
该函数用于在指定卡片时调用。参数 $I, J$ 是 JOI 君翻开的卡片编号。
$I$ 和 $J$ 必须是 $0$ 到 $2N-1$ 之间互不相同的整数。若调用 Flip 时参数不满足此条件,则判为不正确 [1]。
该函数在整数 $A_I$ 和 $A_J$ 相等时返回该值,否则返回 $A_I$ 和 $A_J$ 中对 JOI 君而言更容易记住的那个整数。
若调用该函数的次数超过 $K$ 次,则判为不正确 [2]。
void Answer(int I, int J, int X)
该函数表示你已确定卡片 $I$ 和卡片 $J$ 上写的整数均为 $X$。
参数 $I, J, X$ 必须满足以下条件: $0 \le I \le 2N-1$ $0 \le J \le 2N-1$ $I \neq J$ $A_I = A_J = X$
若调用 Answer 时参数不满足上述条件,则判为不正确 [3]。
参数 $X$ 必须与之前任何一次调用中的参数 $X$ 不同。若不满足此条件,则判为不正确 [4]。
该函数必须恰好调用 $N$ 次。若不满足此条件,则判为不正确 [5]。
你可以自由实现其他辅助函数或声明全局变量。但是,你的提交不得以任何方式与标准输入、标准输出或其他文件进行交互。
子任务
子任务 1 [10 分]
满足以下条件: $T = 1$ $K = 10\,000$ * $P_i = i$($0 \le i \le N-1$)
子任务 2 [50 分]
满足以下条件: $T = 2$ $K = 400$ * $P_i = i$($0 \le i \le N-1$)
子任务 3 [40 分]
满足以下条件: $T = 3$ $K = 300$
样例
输入格式 1
1 3 10000 0 1 2 1 0 2 0 1 2
输出格式 1
Flip(0, 2) -> 1 Flip(0, 4) -> 1 Flip(1, 2) -> 0 Answer(0, 4, 1) Flip(1, 3) -> 0 Flip(5, 2) -> 2 Flip(4, 5) -> 1 Answer(1, 3, 0) Answer(5, 2, 2)
说明
此示例中的函数调用不一定是有意义的调用。