猜猜看

题目描述

hhz 有一个 $1$ 到 $n$ 的排列，你需要猜出它。

你只能问 hhz 以下两个问题：

1. 给定不同的两个数 $i,j$，hhz 会告诉你 $a_i$ 和 $a_j$ 的大小关系。

2. 给定两两不同的 $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\lt n,i\neq j,j\neq k,k\neq i$。

样例交互库

样例交互库以如下格式读入数据：

第一行两个整数 $n, m$。

第二行 $n$ 个整数表示排列。

如果你的交互过程合法且返回排列正确，样例交互库会输出 Accepted cnt=... 表示你使用操作 $2$ 的次数，否则会输出 Wrong Answer [id]，你可以查阅交互库以获得具体错误信息。

数据范围与提示

对于所有数据，$4\leq n\leq 500000,2n\leq m\leq 10^6$。

交互库自适应。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$