QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100 Interactive

# 5033. Y 君的序列

Statistics

题目大意

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\}$ 随机生成。

  • Subtask 1(17pts):$1\le n\le 10,M=10^7$。
  • Subtask 2(7pts):$1\le n\le 150,\forall 1\le i\le n,b_i\equiv (i-1)\pmod n$。
  • Subtask 3(14pts):$1\le n\le 150$。
  • Subtask 4(16pts):$1\le n\le 1000,M=1.5\times10^7$。
  • Subtask 5(16pts):$1\le n\le 5000,M=1.5\times 10^7$。
  • Subtask 6(30pts):$1\le n\le 10^5,M=1.5\times 10^7$。

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

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