← 返回题目列表

AtCoder · arc192_c

C. 范围总和 2

中文机器翻译题面 查看原题

分数: 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 可以从上面显示的查询和响应中唯一确定。