QOJ.ac

QOJ

Limite de temps : 2 s Limite de mémoire : 256 MB Points totaux : 100 Interactif

#403. Memory2

Statistiques

有 $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$ 次以下交互:

  1. 你指定 $2N$ 张卡片中的 $2$ 张。
  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)

说明

此示例中的函数调用不一定是有意义的调用。

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.