Public Judge

pjudge

Time Limit: 2 s Memory Limit: 512 MB Total points: 100 Interactive Hackable ✓

# 21651. 【PR #4】猜猜看

统计

题目描述

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,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$ 个整数。

建议在使用 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