#C. 数据结构是一种艺术(art)

    Type: RemoteJudge 5000ms 2048MiB

数据结构是一种艺术(art)

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

巡最近学会了用树状数组求逆序对。

巡有一个值域 [1,n][1,n] 的未知排列 pp。你每次可以询问一个排列 qq。巡会返回满足在排列 ppii 出现在 jj 前面,在排列 qqii 出现在 jj 后面的有序对 (i,j)(i,j) 的数量。你需要猜出排列 pp

实现细节

你不需要,也不应该实现 int main(),你也不需要文件输入输出。

你无需在程序开头引用头文件 art.h,你只需要在代码开头加入以下代码。

#include <vector>
void answer(std::vector<int>);
int publish(std::vector<int>);

你需要实现一个函数 void solve(int N),这个函数可以调用如下函数:

  • int publish(std::vector<int> q)
    • 该函数可以向交互库询问排列 qqqq 应当是一个值域 [1,n][1,n] 的排列。
    • 该函数至多能被调用 40004000 次。
  • void answer(std::vector<int> q)
    • 该函数向交互库提交答案,表示你猜测的排列。
    • 你必须恰好调用该函数一次。

输入格式

样例交互库从标准输入流读入以下数据:

第一行,一个整数 nn

第二行,nn 个整数,第 ii 个数表示 pip_i

如果输入不符格式,则直接判为 Invalid input!

输出格式

样例交互库向标准输入流输出以下数据:

在你每一次调用 public 函数后,交互库都会输出一行,表示你的交互内容。

在你调用 answer 函数,交互库会输出两行。

第一行,nn 个整数,表示你回答的排列。

第二行会输出交互库的判决。若回答正确会返回 Correct: x published ranking(s).,其中 xx 是你的交互次数。否则返回 Wrong answer!

样例 1

考虑排列 pp{1,3,2}\{1,3,2\}

样例中进行的交互如下:

调用 返回值 解释
publish({1, 2, 3}) 1 合法有序对为 (3,2)(3,2)
publish({2, 3, 1}) 3 合法有序对为 (1,3),(1,2),(3,2)(1,3),(1,2),(3,2)
answer({1, 3, 2}) 回答与正确答案相符

数据范围

  • 子任务 11 (55 分):n6n \leq 6
  • 子任务 22 (1515 分):n40n \leq 40
  • 子任务 33 (1515 分):n250n \leq 250
  • 子任务 44 (1515 分):n444n \leq 444
  • 子任务 55 (2020 分):n2000n \leq 2000
  • 子任务 66 (3030 分):没有特殊限制

对于所有数据,满足 2n40002\leq n \leq 4000

NOIP 2024 模拟赛(三)

Not Attended
Status
Done
Rule
OI
Problem
4
Start at
2024-8-8 8:00
End at
2024-8-8 12:00
Duration
4 hour(s)
Host
Partic.
38