这是一道交互题。
题目描述
你有 $n$ 张卡牌,$n$ 是偶数,每张卡牌上有一个 $1$ 到 $\frac{n}{2}$ 的数字,每个数字恰好出现在两张卡牌上。
你可以选择询问卡牌 $x,y(1\le x,y\le n,x\not=y)$,交互库会随机打乱两张卡牌的顺序并返回给你,之后交互库会再次随机打乱这两张牌的顺序。
你需要在至多 $m$ 次询问确定当前时刻每张卡牌上的数字。
交互方式
你需要引用头文件: "card.h"
。
你需要实现函数: std::vector<int> solve(int n, int m)
,$n,m$ 同题目描述。返回的是一个大小为 $n$ 的 vector
,依次为每张卡片上的数字。
你可以调用函数: std::pair<int, int> query(int x, int y)
需要保证 $1\le x,y\le n,x\not=y$,交互库会返回随机打乱后的两张卡牌。
测试方式
下发文件提供了 grader.cpp
。和 card.cpp
一起编译后得到可执行文件。
在可执行文件中读入以下数据:
第一行一个偶数 $n$,和询问次数限制 $m$。
第二行 $n$ 个 $1$ 到 $\frac{n}{2}$ 的数,每个数字恰好出现两次。
样例输入
(注意样例不满足数据范围中的限制)
6 10
1 3 3 2 1 2
数据范围
$n=10^5$。
对于 $20\%$ 的数据, $m=114514$。
对于另外 $30\%$ 的数据, $m=95000$。
对于另外 $50\%$ 的数据, $m=92200$。