問題一覧 > 通常問題

No.2085 Directed Complete Graph

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 21
作問者 : だれだれ / テスター : niuezniuez kaikeykaikey ぷらぷら
3 ProblemId : 7983 / 自分の提出
問題文最終更新日: 2022-09-26 02:34:49

問題文

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


$N$ 頂点からなる有向グラフが与えられます。頂点には $1$ から $N$ の番号が振られています。

このグラフには $\frac{N(N-1)}{2}$ 本の長さ $1$ の辺があり、以下の性質を満たしています。

  • $1\leq i\lt j \leq N$ を満たすすべての整数の組 $(i, j)$ について、辺 $i \rightarrow j$ または辺 $j \rightarrow i$ のどちらか $1$ つが存在する。
  • あなたは以下の質問を $4000$ 回まで行うことができます。

  • $1\leq a, b\leq N, a \neq b$ を満たす整数の組 $(a, b)$ を選ぶ。$a\to b$ の辺が存在するか聞く。
  • このグラフの最長パス(同じ頂点を $2$ 度通らない)を $1$ つ見つけてください。

    入出力

    まず、頂点数 $N$ が標準入力に与えられます。

    $N$
    

    次に、最長パスが見つかるまで質問を繰り返してください。質問は以下の形式で標準出力に出力してください。

    $?$ $a$ $b$
    

    ただし $1\leq a, b\leq N, a\neq b$ を満たしている必要があります。また、最後に改行してください。

    この質問に対する応答は標準入力に以下の形式で与えられます。

    $T$
    

    ここで $T=0$ または $T=1$ であり、$T=1$ なら $a\to b$ の辺が存在することを、$T=0$ なら存在しないことを表します。

    ただし質問の回数が $4000$ を超えたり、質問の制約が守られていない場合、ジャッジは $T=-1$ を返しただちに終了します。


    最長パスを発見した場合、以下の形式で報告してください。

    $!$
    $L$
    $C_0$ $C_1$ $\ldots$ $C_L$
    

    ここで $L$ は最長パスの長さであり、$C_i (0\leq i \leq L)$ は(この順に)パスが通る頂点を表します。(パスの長さが $L$ なので、通る頂点は $L+1$ 個であることに注意してください。)

    ここで以下の制約が満たされている必要があります。

  • $1\leq i\leq L$ を満たす整数 $i$ について、$C_{i-1}\to C_i$ の辺が存在する。
  • $0\leq i\lt j\leq L$ を満たす整数の組 $(i, j)$ について、$C_i \neq C_j$
  • 考えられる答えが複数存在する場合、どれを出力しても正解と判定されます。

    注意

    各出力後は改行し、必ず flush を行ってください。また質問の結果を必ず受け取ってください。

    答えを出力したあとは、すぐにプログラムを終了してください。

    制約

  • 入力はすべて整数
  • $2\leq N\leq 500$
  • グラフは問題文中の性質をみたす
  • グラフは対話の開始前に決定される
  • サンプル

    サンプル1
    入力
    3
    1
    1
    1
    
    出力
    ? 1 2
    ? 2 3
    ? 3 1
    !
    2
    1 2 3
    

    与えられたグラフには $1\rightarrow 2\rightarrow 3$ のパスがあり、このパスの長さは $2$ です。長さ $3$ 以上のパスはないので、これを出力します。

    $2\rightarrow 3\rightarrow 1$ や $3\rightarrow 1\rightarrow 2$ というパスを出力しても正解となります。

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