[DTCPC 2024] The last permutation
题目背景
**本题题目背景不均为虚构,不影射任何人**。
小 L 是小 L 初中时的白月光。
有一天,小 L 在朋友圈说要玩农,小 L 火速研究怎么下载王者。
第二天,小 L 在朋友圈说要玩吃鸡,小 L 火速研究怎么下载 pubg。
但小 L 很快就和小 L 分手了,小 L 最后的情思化作一个排列。遗憾的是,小 L 并不情愿告诉大家。
不过在你的不断追问下,小 L 还是同意回答几个关于排列的问题。
题目描述
现存在一个长度为 $n$ 的隐藏排列 $p$。你可以进行如下询问若干次:选择三元组 $(l,r,k)$,满足 $1\leq l\leq r\leq n$,$1\leq k\leq r - l + 1$,交互库会返回下标在 $[l,r]$ 内的第 $k$ 大值。
对于一次询问操作,其代价为 $\frac{1}{r-l+1}$,你需要在不超过 $11.8$ 的代价内得出排列。
交互库不自适应,也就是说,你所需得到的排列在交互开始前就已经确定。
输入输出格式
输入格式
输入第一行是一个正整数 $t$ ($1 \le t \le 5$) 表示测试组数。
对于每组数据,输入一行 $n$ ($1 \le n \le 1000$) 表示排列 $p$ 的长度。
当你已经得到排列,你应当输出形如 `! p1 p2 ... pn` 表示你得出的排列。
本题使用 IO 交互模式。
### 交互格式
- `? l r k`,询问下标在 $[l,r]$ 内的第 $k$ 大值。
- `! p1 p2 p3 ... pn`,输出答案。
请注意:在每组数据中,请保证询问操作的代价总和不超过 $11.8$。
需要注意的是,在每一次操作后,需要调用以下函数刷新缓存:
- 对于 C/C++:`fflush(stdout);`
- 对于 C++:`std::cout << std::flush;`
- 对于 Java:`System.out.flush();`
- 对于 Python:`stdout.flush();`
- 对于 Pascal:`flush(output);`
对于其他语言,请自行查阅对应语言的帮助文档。
输出格式
见「交互格式」。
输入输出样例
输入样例 #1
1
5
2
3
1
4
输出样例 #1
? 1 1 1
? 2 2 1
? 3 3 1
? 4 4 1
! 2 3 1 4 5