P17315 [KismetOI 2026 I] Gujyo Senpai and Chin-Lan's Game

郡上与景岚正在玩游戏。她们有一副 $n$ 张牌，点数为 $1$ 至 $n$ 的牌各一张。定义一个牌序列是美好的，当且仅当该牌序列可以由一次下述过程生成： 将这 $n$ 张牌按点数升序排序，将其划分成若干连续段，然后对于每个连续段，选择其中一张牌挪到此段末尾（例如，段 $(1,2,3,4)$ 操作后可以变为 $(2,3,4,1),(1,3,4,2),(1,2,4,3),(1,2,3,4)$），最后将所有段按原顺序拼合起来，得到一个新的序列。 现在景岚设计了一个美好的牌序列并将其背面朝上摆成一排，郡上来猜点数为 $1$ 的牌所在的位置。具体地，郡上会进行多次询问，每次给出一个下标并得知这个位置上牌的点数，直到结果为 $1$ 并结束游戏。郡上非常聪明，所以她每次都会选择可以使**最劣情况**下自己**总查询次数最小**的下标进行询问，注意郡上知道这个序列是美好的。 然而景岚有高超的手法，她可以快速互换郡上尚未查询过的两副牌的位置。为了不被郡上发现，她需要保证游戏结束时，至少存在一个美好的序列使得郡上已知位置的点数与其一致。她希望**最大化**郡上结束游戏时的**查询次数**，并在此基础上**最小化**游戏结束时牌序列的**字典序**。如果游戏结束时仍有未知位置，将牌序列视作所有与已知位置完全匹配的合法牌序列中字典序最小的一个。 现在你来扮演景岚，交互库会进行多次查询，每次查询给定一个下标，你需要返回景岚给出的这个位置上牌的点数。 ### 实现细节 本题是一道函数式交互题。选手不需要，也不应该实现 main 函数，并且不应当向 stdin、stdout 中读入或输出任何字符，否则将视作作弊处理。相应地，选手需要在程序中实现以下函数： ```cpp void init(int c,int n); ``` 对于每个测试点，该函数会在程序开始运行时被评测程序调用恰好一次。$c,n$ 分别表示子任务编号与题目描述中的 $n$。 ```cpp int query(int id); ``` 交互库会在每次查询操作调用这一函数恰好一次，$id$ 表示本次查询操作的下标，此函数需要返回你给出的查询结果。

无。

无。

### 样例 & 样例解释 |交互库调用|选手返回值| |:---:|:---:| |`init(0,5)`|无| |`query(5)`|$5$| |`query(3)`|$4$| |`query(4)`|$3$| |`query(2)`|$2$| |`query(1)`|$1$| 样例展示了一组可能的交互过程，$n=5$，郡上依次查询了 $5,3,4,2,1$ 位置，景岚构造的牌序列是 $1,2,4,3,5$。可以证明该序列是美好的，最大化了郡上的查询次数，并且在所有符合条件的序列中字典序最小。 ### 数据范围 对所有数据，满足 $1\le n\le 5\times 10^6$。 ::cute-table{tuack} |子任务编号|$n\le $|特殊性质|分值| |:---:|:---:|:---:|:---:| |#1|$3$|无|$10$| |#2|$10$|^|$10$| |#3|$20$|^|$20$| |#4|$10^5$|^|$20$| |#5|^|有|$10$| |#6|$5\times 10^6$|^|$10$| |#7|^|无|$20$| 特殊性质：当郡上有多个符合条件的查询位置时，她会选择下标最小的位置进行查询。