CF1056C Pick Heroes

不要告诉我你认为我能成为什么。 如果你说 Arkady 玩跳棋有点老派，那你就错了。他和他的朋友们还热衷于一款现代电脑游戏。我们不讨论这款游戏的规则，唯一与本题相关的特性是：每位玩家在游戏开始时必须选择一个不同的英雄。 有 $2$ 支队伍，每队有 $n$ 名玩家，共有 $2n$ 个英雄要分配给两队。两队轮流选择英雄：首先第一队在自己的队伍中选择一个英雄，然后第二队选择一个英雄，如此交替进行。注意，一旦某个英雄被选中，双方都无法再选择该英雄。 朋友们对第 $i$ 个英雄的战斗力评估为 $p_i$。每支队伍都希望最大化自己队伍中英雄的总战斗力。然而，有一个例外：有 $m$ 对英雄彼此之间特别克制，因此当某队选择了这对中的一个英雄时，另一队必须在其回合选择该对中的另一个英雄。每个英雄最多只会出现在一对这样的组合中。 这是一个交互题。你需要编写一个程序，为一支队伍最优地选择英雄，而评测程序将为另一队进行选择。注意，评测程序可能不会选择最优解，这时你应抓住机会，尽可能让你的队伍总战斗力最大化。形式化地说，如果你有机会无论评测程序如何选择都能达到总战斗力 $q$ 或更高，你必须达到 $q$ 或更高才能通过测试。

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^3$，$0 \le m \le n$），分别表示每队的玩家数和特殊英雄对的数量。 第二行包含 $2n$ 个整数 $p_1, p_2, \ldots, p_{2n}$（$1 \le p_i \le 10^3$），表示每个英雄的战斗力。 接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$（$1 \le a, b \le 2n$，$a \ne b$），表示一对彼此特别克制的英雄。保证每个英雄最多只会出现在一对中。 再下一行包含一个整数 $t$（$1 \le t \le 2$），表示你所代表的队伍编号。如果 $t=1$，则你先手，否则你后手。 Hack 格式 为了进行 Hack，请在上述格式后再输出一行。在这一行中输出 $2n$ 个从 $1$ 到 $2n$ 的不同整数，表示评测程序队伍的优先选择顺序。评测程序每次会从这个列表中选择第一个可选的英雄（即尚未被选中且不违反特殊英雄对规则的英雄）。

轮到你行动时，输出一个整数 $x$（$1 \le x \le 2n$），表示你选择的英雄编号。注意，你不能选择已被双方选中的英雄，且必须遵守特殊英雄对的规则。 轮到对方行动时，读入一行，包含一个整数 $x$（$1 \le x \le 2n$），表示对方选择的英雄编号。保证该编号未被选中，且对方也遵守特殊英雄对的规则。 最后一轮结束后，你应立即终止程序，不要再输出任何内容。 每次输出后请务必输出换行并刷新输出缓冲区，否则会因“Idleness limit exceeded”而判错。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请查阅相关文档 如果评测程序返回 $-1$，表示你做出了非法操作。此时应立即退出程序，你会看到 Wrong answer 的判定。否则，如果你继续读取已关闭的输入流，可能会得到任意判定结果。

在第一个样例中，你先手。例如，你选择 $6$，对方被迫选择 $2$。你选择 $5$，对方选择 $4$。最后你选择 $3$，对方选择 $1$。 在第二个样例中，你后手。对方选择 $6$，你选择 $5$，迫使对方选择 $1$。然后你选择 $4$，对方选择 $3$，你选择 $2$。 由 ChatGPT 4.1 翻译