• 比赛：EJOI 2026 Day 1
• 时间限制：2 秒
• 内存限制：1024 MiB
• 题目类型：交互题

题目描述

Iliyan 把一个排列藏了起来：

$p_0,p_1,\dots,p_{N-1}$，

它是整数 $0,1,\dots,N-1$ 的一个排列。

你可以进行询问。每次选择两个下标 $i,j$，其中 $0\le i,j<N$，交互库会告诉你

$p_i\oplus p_j$，

其中 $\oplus$ 表示按位异或。

Iliyan 最多允许你进行 $Q$ 次询问。

但是，即使知道了一些甚至全部两两异或值，也不一定能够唯一确定隐藏排列。

定义另一个排列 $a_0,a_1,\dots,a_{N-1}$ 与 $p$ 不可区分，当且仅当对任意 $0\le i,j<N$ 都有

$a_i\oplus a_j=p_i\oplus p_j$。

如果隐藏排列是 $p$ 或 $a$，所有可能询问的答案都完全相同，因此任何询问策略都无法区分它们。

你的任务是找出：

与隐藏排列 $p$ 不可区分的所有排列中字典序最小的一个。

排列 $x$ 比排列 $y$ 字典序更小，是指在第一个满足 $x_k\ne y_k$ 的位置 $k$ 上，有 $x_k<y_k$。

隐藏排列在程序运行前就已固定，并不会根据你的询问改变。

实现要求

实现：

std::vector<int> solve(int N);

• N：排列长度。

该函数共调用 $T$ 次，每次对应一个隐藏排列。

你必须返回与当前隐藏排列不可区分的字典序最小排列。

交互函数

可以调用：

int get_xor(int i, int j);

返回 $p_i\oplus p_j$。

必须保证 $0\le i,j<N$，否则会得到 Output isn't correct: Invalid argument。

该函数可以认为在 $O(1)$ 时间内返回。

每个子任务中的询问上限 $Q$ 是固定的，不会作为参数传给你的程序。

数据范围

对于第 $i$ 次 solve 调用，记其排列长度为 $N_i$：

• $1\le N_i\le2^{20}$；
• $1\le T\le2^{10}$；
• $T\cdot\max(N_1,N_2,\dots,N_T)\le2^{25}$；
• 第 $i$ 次调用最多允许 $Q_i$ 次询问，其中 $Q_i$ 根据子任务等于 $N_i$ 或 $N_i^2$。

交互样例

假设 solve 被调用两次。

第一次调用：

Jury:        solve(4)

Participant: get_xor(0,1)
Jury:        2

Participant: get_xor(0,2)
Jury:        3

Participant: get_xor(0,3)
Jury:        1

Participant: get_xor(1,2)
Jury:        1

Participant: get_xor(1,3)
Jury:        3

Participant: get_xor(2,3)
Jury:        2

Participant: return {0,2,3,1}

第二次调用：

Jury:        solve(1)
Participant: return {0}

样例说明

第一次调用中，隐藏排列为

[2,0,1,3]

但与它不可区分的字典序最小排列为

[0,2,3,1]。

共进行了 6 次询问。该子任务中 $Q_1=N_1^2=16$，因此合法。

第二次调用时 $N_2=1$，唯一排列就是 [0]。

子任务

子任务	分值	$N_i$	$T$	$Q_i$	额外限制
0		-		$N_i^2$	样例
1	7	$\le2^3$	$2^{10}$		无
2	18	$\le2^7$	$2^5$
3	5	$\le2^{11}$
4				$N_i$
5		$\le2^{18}$			$N_i=2^k$，其中 $k$ 为整数
6					$N_i$ 为奇数
7	30				无
8	25	$\le2^{20}$

Sample grader

输入格式：

• 第一行两个整数 $T,Q_{\text{type}}$，其中 $Q_{\text{type}}\in\{1,2\}$；
• 随后 $2T$ 行描述各测试：
  • 第 $2i$ 行：一个整数 $N_i$；
  • 第 $2i+1$ 行：$N_i$ 个整数，表示隐藏排列。

若 $Q_{\text{type}}=1$，则第 $i$ 次调用的询问上限为 $Q_i=N_i$。

若 $Q_{\text{type}}=2$，则 $Q_i=N_i^2$。

输出第 $i$ 次 solve 返回的排列。