Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Etkileşimli
İstatistikler

Deskripsi

Terdapat sebuah graf berarah dengan $n$ simpul yang dinomori dari $1$ hingga $n$. Untuk setiap simpul $1 \le i \le n$, derajat keluar dari simpul $i$ paling banyak satu; dengan demikian kita dapat mendeskripsikan graf tersebut menggunakan sebuah larik $p_i$, di mana $p_i = 0$ jika derajat keluar dari simpul $i$ adalah nol, dan selain itu $1 \le p_i \le n$, $p_i \ne i$, serta terdapat sisi berarah dari $i$ ke $p_i$. Tidak ada siklus berarah di dalam graf, sehingga dari simpul $i$ mana pun, lintasan yang terbentuk dengan terus berpindah ke simpul berikutnya sepanjang sisi berarah pada akhirnya akan berhenti di sebuah simpul dengan derajat keluar nol.

Pada awalnya, terdapat sebuah bidak kayu di salah satu simpul. Ketika Anda bertepuk tangan, jika bidak berada di simpul $i$ dengan $p_i$ tak nol, maka bidak akan berpindah ke simpul $p_i$; jika tidak, bidak tidak berpindah. Namun, Anda sama sekali tidak dapat melihat di mana bidak tersebut berada — satu-satunya operasi yang dapat Anda lakukan adalah memilih suatu himpunan bagian simpul, meletakkan bidak di salah satu simpul pilihan Anda, bertepuk tangan beberapa kali, dan mengamati apakah bidak berakhir di salah satu simpul pilihan Anda. Bahkan peletakan awal bidak dan banyaknya tepukan tangan dipilih oleh interaktor: Anda hanya dapat memilih himpunan bagian simpul, dan mengamati jumlah maksimum tepukan tangan sedemikian sehingga bidak dapat mulai di salah satu simpul pilihan Anda dan berakhir di salah satu simpul pilihan Anda.

Anda ingin menambahkan satu sisi dari $x$ ke $y$ ($1 \le x, y \le n$, $x \ne y$, dan $p_x = 0$, yaitu Anda dapat menetapkan $p_x = y$), sehingga Anda dapat bertepuk tangan lebih banyak kali lagi pada keseluruhan graf dibandingkan sebelumnya. Namun, penambahan sisi tersebut tetap tidak boleh menciptakan siklus berarah apa pun di dalam graf.

Temukan sisi mana pun yang dapat Anda tambahkan dengan melakukan kueri jumlah maksimum tepukan tangan pada paling banyak $n$ himpunan bagian simpul, atau tentukan bahwa mustahil untuk menambahkan sisi semacam itu.

Masukan

Baris pertama masukan berisi sebuah bilangan bulat $n$ ($1 \le n \le 1000$).

Interaksi

Untuk melakukan kueri, cetak satu baris berbentuk $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, di mana $1 \le k \le n$, dan $1 \le u_i \le n$ adalah simpul-simpul yang saling berbeda dalam himpunan bagian pilihan Anda. Kemudian baca satu baris berisi sebuah bilangan bulat: jumlah maksimum tepukan tangan sedemikian sehingga bidak dapat mulai di salah satu simpul pilihan Anda dan berakhir di salah satu simpul pilihan Anda. Anda dapat melakukan paling banyak $n$ kueri.

Setelah Anda menentukan sisi yang ingin ditambahkan, cetak satu baris berbentuk $\texttt{! } x \text{ } y$, di mana $1 \le x, y \le n$ adalah titik-titik ujung dari sisi berarah yang ingin Anda tambahkan. Jika terdapat beberapa solusi, Anda boleh mencetak yang mana saja.

Jika mustahil untuk menambahkan sisi semacam itu, cetak $-1 \text{ -1}$ sebagai pengganti titik-titik ujung sisi.

Solusi Anda harus berhenti segera setelah mencetak jawaban.

Lakukan flush pada keluaran setelah setiap kueri yang Anda buat.

Interaktor tidak adaptif; graf sudah ditetapkan sebelumnya.

Contoh

6

2

1

2
? 4 1 2 3 4

? 2 5 6

? 3 4 5 6

! 5 1

Catatan

problem_17169_c1d82052e4ed01f4f4f5920c82dcbcb1.png

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1220EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.