Y 君的序列 - 题目

Y 君有一个长度为 $n$ 的序列 $\{a_n\}$，初始时 $\forall 1\le i\le n,a_i=i$。

他可以进行若干次如下的操作，目标是将序列转变为另一个给定的序列 $\{b_n\}$，即 $\forall 1\le i\le n,a_i=b_i$。保证 $\{b_n\}$ 是一个 $1$ 到 $n$ 的排列。

1.选择 $i,j$ 满足 $1\le i,j\le n,i\neq j,2|a_i$

2.设 $x=a_i/2$，令 $a_j$ 加上 $x$，$a_i$ 减去 $x$

Y 君想知道，他的目标是否可以在有限步内达成。如果可以，还请你给出一种步数尽量少的操作方案。

注意你不需要最小化操作的步数，只要你正确判断了是否有解、给出的方案合法、且步数不超过一个给定的值 $M$，就算作答案正确。具体的限制可以看【数据范围】。你还需要保证在操作的过程中，序列中的所有值位于 $[1,10^9]$ 内。可以证明，如果有解，则一定可以在本题的限制下得出至少一种方案。

为了避免较大的输出量，本题采用交互的形式进行。

你需要实现函数 void SEQ(int n,int M)，其中 $n,M$ 与题面含义一致。

你可以通过调用 int Get(int x) 来获取 $b[x]$ 的值。同一个 $x$ 允许调用多次，但你必须保证 $1\le x\le n$。

接着，你需要恰好调用一次函数 void answer(int flag)，表示你判断是否有解。用 flag=1 表示有解，flag=0 表示无解。在有解的情况下，你需要再调用若干次 void add(int i,int j) ，表示操作 $i,j$。

请注意调用函数的顺序。

将所有下发文件放置在同一目录下，在终端使用 g++ sample-grader.cpp seq.cpp -o seq 进行编译，使用 ./seq < seq.in 运行。

你可以在示例程序 sample-seq.cpp 的基础之上进行程序的编写。

保证在一个测试点中，交互库调用恰好一次函数 SEQ。

第一行，三个整数，$n,M,F$。其中 $F$ 表示该组数据是否有解，你返回的 $flag$ 应与 $F$ 相等。

第二行，$n$ 个正整数，表示排列 $\{b_n\}$。

5 10000000 1
4 2 5 1 3

这组数据是有解的，一种可能的方案为：依次操作 $(i,j)$ = $(4,3),(4,5),(5,1)$。

序列 $\{a_n\}$ 的变化是：1 2 3 4 5 $\rightarrow$ 1 2 5 2 5 $\rightarrow$ 1 2 5 1 6 $\rightarrow$ 4 2 5 1 3.

对于所有数据，保证 $1\le n\le 10^5,1.5\times 10^6\le M\le 1.5\times 10^7$。

保证对于 $n > 1000$ 的测试点，$\{b_n\}$ 随机生成。

子任务之间可能存在合法的依赖关系。

保证最终交互库与下发交互库的差异仅为添加了反作弊机制，以及输入输出格式可能存在差异（但是你的程序不应有任何的输出，也不应该实现任何主函数）。

QOJ.ac