题目描述
hhz 有一个 $1$ 到 $n$ 的排列,你需要猜出它。
你只能问 hhz 以下两个问题:
- 给定不同的两个数 $i,j$,hhz 会告诉你 $a_i$ 和 $a_j$ 的大小关系。
- 给定两两不同的 $i,j,k$,hhz 会告诉你 $a_i,a_j,a_k$ 的中位数。
你只能进行 $2$ 次询问 $1$ 和 $m$ 次询问 $2$,你需要猜出这个排列。
任务
这是一道交互题。
你必须包含头文件 guess.h
。
你需要实现如下函数:
vector<int> solve(int n, int m);
这个函数只会被调用一次。你需要返回一个长为 $n$ 的数组表示排列。
你可以调用如下过程:
bool query1(int i, int j);
若 $a_i\lt a_j$ 这个函数返回 $1$,否则返回 $0$。
你需要保证 $0\leq i,j\lt n$,$i\neq j$。
int query2(int i, int j, int k);
这个函数返回 $a_i,a_j,a_l$ 的中位数。
你需要保证 $0\leq i,j,k\lt n$,$i\neq j$,$j\neq k$,$k\neq i$。
样例交互库
样例交互库以如下格式读入数据:
第一行两个整数 $n, m$。
第二行 $n$ 个整数表示排列。
如果你的交互过程合法且返回排列正确,样例交互库会输出 Accepted cnt=...
表示你使用操作 $2$ 的次数,否则会输出 Wrong Answer [id]
,你可以查阅交互库以获得具体错误信息。
数据范围与提示
本题捆绑测试。
子任务编号 | $n\leq$ | $m=$ | 分值 |
---|---|---|---|
$1$ | $100$ | $n^3$ | $20$ |
$2$ | $1000$ | $n^2$ | $20$ |
$3$ | $3\cdot 10^5$ | $3n$ | $30$ |
$4$ | $5\cdot 10^5$ | $2n$ | $30$ |
对于所有数据,$50\leq n\leq 5\cdot 10^5$,$2n\leq m\leq 10^6$。
交互库自适应。
时间限制:$2\texttt{s}$
空间限制:$512\texttt{MB}$
Hacks
你可以通过以下格式来提交 Hack:
- $seed$
- $n$ $m$ $mode$ $arg_1$ $arg_2$ $\cdots$ $arg_k$
其中各个参数的含义如下:
- $seed$:用于随机的种子,其需满足 $0 \leq seed < 2^{31} = 2\,147\,483\,648$。
- $n$:即题意中的 $n$。其需满足 $50 \leq n \leq 5 \cdot 10^5$。
- $m$:即题意中的 $m$。其需满足 $2n\leq m\leq 10^6$。
- $mode$:交互库所使用的策略。你需要满足 $0 \leq mode \leq 3$:
- 当 $mode = 0$ 时:
- 交互库将随机一个排列作为 $a$。
- 参数个数 $k=0$,即对应的输入的第二行只有三个整数。
- 当 $mode = 1$ 时:
- 交互库 adaptive,将根据选手的询问动态构造 $a$。
- 参数个数 $k=1$,其包含恰好一个参数 $init\_num$,其需满足 $0 \leq init\_num < n$。即对应的输入的第二行只有四个整数。
- 当 $mode = 2$ 时:
- 交互库 adaptive,将根据选手的询问动态构造 $a$。
- 参数个数 $k=1$,其包含恰好一个参数 $rev$,其需满足 $0 \leq rev \leq 1$。即对应的输入的第二行只有四个整数。
- 当 $mode = 3$ 时:
- 将使用你输入的排列作为 $a$。
- 参数个数 $k=n$,其包含 $n$ 个参数 $a_1,a_2,\cdots,a_n$,满足排列 $a$。即对应的输入的第二行只有 $n+3$ 个整数。
- 当 $mode = 0$ 时:
建议在使用 Hack 时,总是使用 $mode = 3$。下面是四组合法的输入数据供你参考:
123456
50 1000000 0
234567
50 1000000 1 1
123123
50 1000000 2 0
67812345
50 1000000 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50