Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:512 MB
Statistics

这是一道交互题。

题目描述

你有 $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$。

下发文件