QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

# 8356. 猜猜看

Statistics

猜猜看

题目描述

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],你可以查阅交互库以获得具体错误信息。

数据范围与提示

子任务编号 $n\leq$ $m=$ 分值
$1$ $100$ $n^3$ $21$
$2$ $1000$ $n^2$ $22$
$3$ $500000$ $2n$ $57$

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

交互库自适应。

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

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