[DTCPC 2024] The last permutation

Luogu

IDLGP10159

Time1000ms

Memory512MB

DifficultyP6

2024交互题Special Judge剪枝构造洛谷月赛

现存在一个长度为 $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$ 的代价内得出排列。交互库不自适应，也就是说，你所需得到的排列在交互开始前就已经确定。 ## Input 输入第一行是一个正整数 $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);` 对于其他语言，请自行查阅对应语言的帮助文档。 ## Output 见「交互格式」。 [samples] ## Background **本题题目背景不均为虚构，不影射任何人**。小 L 是小 L 初中时的白月光。有一天，小 L 在朋友圈说要玩农，小 L 火速研究怎么下载王者。第二天，小 L 在朋友圈说要玩吃鸡，小 L 火速研究怎么下载 pubg。但小 L 很快就和小 L 分手了，小 L 最后的情思化作一个排列。遗憾的是，小 L 并不情愿告诉大家。不过在你的不断追问下，小 L 还是同意回答几个关于排列的问题。

Samples

Input #1

Output #1


? 1 1 1

? 2 2 1

? 3 3 1

? 4 4 1

! 2 3 1 4 5

API Response (JSON)

{
  "problem": {
    "name": "[DTCPC 2024] The last permutation",
    "description": {
      "content": "现存在一个长度为 $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$ 的代价内得出排列。 交互库不自适应，也就",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10159"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "现存在一个长度为 $n$ 的隐藏排列 $p$。你可以进行如下询问若干次：选择三元组 $(l,r,k)$，满足 $1\\leq l\\leq r\\leq n$，$1\\leq k\\leq r - l + 1$，交互库会返回下标在 $[l,r]$ 内的第 $k$ 大值。\n\n对于一次询问操作，其代价为 $\\frac{1}{r-l+1}$，你需要在不超过 $11.8$ 的代价内得出排列。\n\n交互库不自适应，也就...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments