C - Range Sums 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

この問題はインタラクティブな問題です。

正整数 N が与えられます。

すぬけくんは、(1,2,\dots,N) を並び替えた正整数列 P=(P_1,P_2,\dots,P_N) と、長さ N の正整数列 A=(A_1,A_2,\dots,A_N) を隠し持っています。ここで、P_1<P_2 が保証されます。

あなたは、すぬけくんに 2N 回までクエリを送ることができます。クエリは以下のようなものです。

  • 1\leq s,t\leq N なる相異なる正整数 s,t を指定し、\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 回以下クエリを送ることができます。相異なる正整数 s,t を指定してクエリを送るとき、以下のように出力してください。末尾に改行を入れることを忘れないでください。

? s t

クエリを送ると、すぬけくんからの返答が以下の形式で標準入力から与えられます。

X

ここで、X は整数で、

  • X\ne -1 のとき \displaystyle \sum_{i=\min(P_s,P_t)}^{\max(P_s,P_t)}A_i の値が X であることを表します。
  • 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

このときも、プログラムはすでに不正解とみなされています。ただちにプログラムを終了してください。

注意点

  • 出力を行うたびに、末尾に改行を入れて標準出力をflushしてください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
  • 解答を出力したとき、または -1 を標準入力から受け取ったとき、ただちにプログラムを終了してください。そうしなかった場合の判定結果は不定です。
  • 余計な改行は不正なフォーマットの出力とみなされることに注意してください。
  • この問題のジャッジシステムは適応的ではありません。 つまり、P と A はジャッジとの対話前に決定され、いかなるタイミングでも変更されることはありません。

入出力例

N=6,P=(2,4,6,5,3,1),A=(1,9,2,25,2,9) のときの対話の一例を示します。

入力 出力 説明
6 まず整数 N が標準入力から与えられます。
? 1 2 s=1,t=2 としてすぬけくんにクエリを送ります。
36 出力は制約を満たしているので、\displaystyle \sum_{i=\min(P_1,P_2)}^{\max(P_1,P_2)}A_i の値である 36 が与えられます。
? 2 5 s=2,t=5 としてすぬけくんにクエリを送ります。
27 出力は制約を満たしているので、\displaystyle \sum_{i=\min(P_2,P_5)}^{\max(P_2,P_5)}A_i の値である 27 が与えられます。
! 2 4 6 5 3 1 1 9 2 25 2 9 P と A が特定できたことを報告します。この出力の後、ただちにプログラムを終了することで正解と判定されます。

これは対話の一例であることに注意してください。特に、ここまでのクエリとその返答で P と A を確実に特定できるとは限りません。

Score : 600 points

Problem Statement

This problem is interactive.

You are given a positive integer N.

Snuke secretly holds a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N) and a sequence A=(A_1,A_2,\dots,A_N) of positive integers of length N. It is guaranteed that P_1<P_2.

You may send up to 2N queries to Snuke. A query is of the following form:

  • Specify two distinct positive integers s and t with 1\leq s,t\leq N, and you will be given the value of \displaystyle \sum_{i=\min(P_s,P_t)}^{\max(P_s,P_t)}A_i.

Determine P and A.

Constraints

  • 3\leq N\leq 5000
  • 1\leq P_i\leq N (1\leq i\leq N)
  • P_i\ne P_j for i\ne j.
  • P_1<P_2
  • 1\leq A_i\leq 10^9 (1\leq i\leq N)
  • N, P_i, and A_i are integers.
  • P and A are fixed before the interaction with the judge.

Input/Output

This problem is interactive.

First, N is given from Standard Input:

N

Next, you may send at most 2N queries to Snuke. When sending a query by specifying two distinct positive integers s,t, output in the following format. Do not forget to include a newline at the end.

? s t

After sending a query, you will receive a response from Snuke in the following format:

X

Here, X is an integer:

  • If X\ne -1, then X is the value of \displaystyle \sum_{i=\min(P_s,P_t)}^{\max(P_s,P_t)}A_i.
  • If X=-1, then either s,t do not satisfy the constraints or you have sent more than 2N queries.
    • In this case, your program is judged as incorrect and must terminate immediately.

Once you have determined P and A, output your answer in the following format. This output does not count as a query.

! P_1 P_2 \dots P_N A_1 A_2 \dots A_N

Note that P_1<P_2. After this output, terminate your program immediately.

If you output anything that does not follow the above formats, -1 will be given as input.

-1

In that case, your program is judged as incorrect and must terminate immediately.

Notes

  • After every output, be sure to end with a newline and flush the standard output. Failure to do so may result in a TLE.
  • When you output your answer, or receive -1 from standard input, terminate your program immediately. Otherwise, the outcome is indeterminate.
  • Note that extra newlines may be considered as an output format error.
  • The judge system for this problem is not adaptive. That is, P and A are determined before the interaction with the judge and will not be changed at any point.

Sample Interaction

For N=6, P=(2,4,6,5,3,1), and A=(1,9,2,25,2,9), here is an example of an interaction.

Input Output Explanation
6 First, the integer N is given from standard input.
? 1 2 A query is sent to Snuke with s=1, t=2.
36 Since the query satisfies the constraints, the value 36, which is equal to \displaystyle \sum_{i=\min(P_1,P_2)}^{\max(P_1,P_2)}A_i, is returned.
? 2 5 A query is sent to Snuke with s=2, t=5.
27 Since the query satisfies the constraints, the value 27, which is equal to \displaystyle \sum_{i=\min(P_2,P_5)}^{\max(P_2,P_5)}A_i, is returned.
! 2 4 6 5 3 1 1 9 2 25 2 9 You report that P and A have been determined. After this output, the program should terminate immediately, and it will be judged as correct.

Note that this is just one example of an interaction. In particular, it is not guaranteed that P and A can be uniquely determined from the queries and responses shown above.