問題一覧 > 通常問題

No.2577 Simple Permutation Guess

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (AC するまで非表示) / 解いたユーザー数 45
作問者 : null / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 9689 / 自分の提出
問題文最終更新日: 2023-12-05 00:12:21
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2023 (順位表) の他の問題:

Problem Statement

The judge has a permutation $P$ of length $n$. Given only $n$, guess the permutation $P$ using the following query at most $\lfloor \lfloor (n - 1) \log_2 n \rfloor - \frac{n - 1}{2} +1 \rfloor$ times.

Query: send a permutation $Q$. You obtain whether $Q \le P$ holds.

Here, a permutation of length $n$ is a rearrangement of $1, 2, \dots, n$. Also, $Q \le P$ means that either $Q_i=P_i$ for all $1 \le i \le n$, or there exists some $j$ such that $Q_i=P_i$ for all $1 \le i < j$ and $Q_j < P_j$.

About the Judge

The judge of this problem is adaptive. The judge may change $P$ as long as it does not contradict its responses to the queries.

Addendum: Fixed a typo (corrected "ジャッジについてについて" to "ジャッジについて") (0:12)

About the Evil Cases

In this problem, the constraints are kept small because of the speed of the reactive judge, but evil cases (see "正解判定のポリシー" (Policy on Judging Correct Answers) here) are included to distinguish fast solutions. The results of these cases do not affect the judge result.

Constraints

  • $1 \le n \le 250$
  • $P$ is a permutation.
  • All inputs are integers.

Constraints of the Evil Cases

  • $250 < n \le 400$
  • $P$ is a permutation.
  • All inputs are integers.

Input and Output

First, an integer $n$ is given.

$n$

Next, you may send queries in the following format at most $\lfloor \lfloor (n - 1) \log_2 n \rfloor - \frac{n - 1}{2} +1 \rfloor$ times. Here, the sequence $Q$ must be a permutation.

$?\ Q_1\ Q_2\ \dots\ Q_n$

You are given $ret=1$ if $Q \le P$, $ret=0$ if $Q>P$, and $ret=-1$ if there was some problem with the judge.

$ret$

Here, if $ret = -1$, terminate your program immediately. Otherwise, either continue querying or answer with a permutation.

To answer with a permutation, output it in the following format. This output is not counted as a query.

$!\ Q_1\ Q_2\ \dots\ Q_n$

After that, terminate your program immediately.

Notes

  • After each output, print a trailing newline and flush the output.
  • The judge's behavior for invalid output or actions may be undefined.

Sample

This is one example of an interaction and may not be an optimal way of sending queries.
InputOutputExplanation
5$n=5$
? 1 2 3 4 5Sent a query with $Q=1, 2, 3, 4, 5$.
1The response to the query was $Q \le P$.
? 5 4 3 2 1Sent a query with $Q=5, 4, 3, 2, 1$.
0The response to the query was $Q>P$.
? 2 5 1 4 3Sent a query with $Q=2, 5, 1, 4, 3$.
1The response to the query was $Q \le P$.
? 2 5 4 3 1Sent a query with $Q=2, 5, 4, 3, 1$.
1The response to the query was $Q \le P$.
! 2 5 4 3 1Sent an answer with $Q=2, 5, 4, 3, 1$.
The judge result is WA. It was $P=2,5,4,3,1$, but since, for example, $P=5,4,3,1,2$ also does not contradict the queries so far, the judge changed $P$.
For example, if you send the following query before answering, the permutation is uniquely determined and the judge result is AC.
InputOutputExplanation
? 3 1 2 4 5Sent a query with $Q=3, 1, 2, 4, 5$.
0The response to the query was $Q > P$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。