分数: 600 点
问题陈述
这个问题是交互式的。
给你一个正整数 N.
Snuke 秘密持有排列 P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N) 和一个序列 A=(A_1,A_2,\dots,A_N) 长度为正整数 N. 保证 P_1<P_2.
您最多可以发送 2N 向 Snuke 查询。查询具有以下形式:
- 指定两个 不同 正整数 s 和 t 与 1\leq s,t\leq N,您将获得以下值 \displaystyle \sum_{i=\min(P_s,P_t)}^{\max(P_s,P_t)}A_i.
确定 P 和 A.
约束
- 3\leq N\leq 5000
- 1\leq P_i\leq N (1\leq i\leq N)
- P_i\ne P_j 为 i\ne j.
- P_1<P_2
- 1\leq A_i\leq 10^9 (1\leq i\leq N)
- N, P_i,和 A_i 是整数。
- P 和 A 在与法官互动之前已修复。
输入/输出
这个问题是交互式的。
首先, N 由标准输入给出:
N
接下来,您最多可以发送 2N 向 Snuke 查询。通过指定两个发送查询时 不同 正整数 s,t,按以下格式输出。不要忘记在末尾添加换行符。
? s t
发送查询后,您将收到 Snuke 的以下格式的响应:
X
在这里, X 是一个整数:
- If X\ne -1,那么 X 的值 \displaystyle \sum_{i=\min(P_s,P_t)}^{\max(P_s,P_t)}A_i.
- If X=-1,然后 s,t 不满足限制或您已发送超过 2N 查询。
- 在这种情况下,您的程序被判断为不正确,必须立即终止。
一旦您确定 P 和 A,按以下格式输出您的答案。此输出不算作查询。
! P_1 P_2 \dots P_N A_1 A_2 \dots A_N
请注意 P_1<P_2. 在此输出之后,立即终止程序。
如果您输出任何不遵循上述格式的内容, -1 将作为输入给出。
-1
在这种情况下,您的程序将被判断为不正确,必须立即终止。
注释
- 每次输出后,请务必以换行符结束并刷新标准输出。如果不这样做可能会导致 TLE.
- 当您输出答案或收到
-1从标准输入,立即终止您的程序。否则,结果是不确定的。 - 请注意,额外的换行符可能会被视为输出格式错误。
- 该问题的判断系统不具有自适应性。 也就是说, P 和 A 在与评委互动之前确定,并且在任何时候都不会更改。
示例交互
对于 N=6, P=(2,4,6,5,3,1),和 A=(1,9,2,25,2,9),这是一个交互示例。
| 输入 | 输出 | 说明 |
|---|---|---|
6 |
一、整数 N 由标准输入给出。 | |
? 1 2 |
查询被发送到 Snuke s=1, t=2. | |
36 |
由于查询满足约束,因此值 36,等于 返回 \displaystyle \sum_{i=\min(P_1,P_2)}^{\max(P_1,P_2)}A_i。 | |
? 2 5 |
查询被发送到 Snuke s=2, t=5. | |
27 |
由于查询满足约束,因此值 27,等于 返回 \displaystyle \sum_{i=\min(P_2,P_5)}^{\max(P_2,P_5)}A_i。 | |
! 2 4 6 5 3 1 1 9 2 25 2 9 |
您报告说 P 和 A 已确定。此输出后,程序应立即终止,并判断其正确。 |
请注意,这只是交互的一个示例。特别是,不保证 P 和 A 可以从上面显示的查询和响应中唯一确定。