Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Interactivo
Estadísticas

คำอธิบาย

มีกราฟระบุทิศทางที่มี $n$ จุดยอด หมายเลข $1$ ถึง $n$ สำหรับแต่ละจุดยอด $1 \le i \le n$ ดีกรีออกของจุดยอด $i$ มีค่าไม่เกินหนึ่ง ดังนั้นเราจึงสามารถอธิบายกราฟด้วยอาร์เรย์ $p_i$ โดยที่ $p_i = 0$ หากดีกรีออกของจุดยอด $i$ เป็นศูนย์ และมิฉะนั้น $1 \le p_i \le n$, $p_i \ne i$ และมีเส้นเชื่อมระบุทิศทางจาก $i$ ไปยัง $p_i$ ในกราฟไม่มีวัฏจักรระบุทิศทาง ดังนั้นจากจุดยอด $i$ ใดๆ เส้นทางที่เกิดจากการเคลื่อนที่ไปยังจุดยอดถัดไปตามเส้นเชื่อมระบุทิศทางซ้ำๆ จะสิ้นสุดลงที่จุดยอดที่มีดีกรีออกเป็นศูนย์ในที่สุด

ในตอนแรก มีหมากฮอสไม้วางอยู่บนจุดยอดจุดหนึ่ง เมื่อคุณปรบมือ หากหมากฮอสอยู่บนจุดยอด $i$ ที่มี $p_i$ ไม่เป็นศูนย์ มันจะเคลื่อนที่ไปยังจุดยอด $p_i$ มิฉะนั้นมันจะไม่เคลื่อนที่ อย่างไรก็ตาม คุณไม่สามารถมองเห็นได้เลยว่าหมากฮอสอยู่ที่ไหน — การดำเนินการเดียวที่คุณทำได้คือเลือกสับเซตของจุดยอด วางหมากฮอสลงบนจุดยอดหนึ่งในกลุ่มที่คุณเลือก ปรบมือจำนวนหนึ่ง แล้วสังเกตว่าหมากฮอสไปหยุดอยู่ที่จุดยอดหนึ่งในกลุ่มที่คุณเลือกหรือไม่ แม้แต่ตำแหน่งเริ่มต้นของหมากฮอสและจำนวนครั้งที่คุณปรบมือก็ถูกเลือกโดยอินเทอร์แอกเตอร์: คุณทำได้เพียงเลือกสับเซตของจุดยอด และสังเกตจำนวนครั้งสูงสุดที่คุณสามารถปรบมือได้โดยที่หมากฮอสสามารถเริ่มต้นบนจุดยอดหนึ่งในกลุ่มที่คุณเลือกและจบลงบนจุดยอดหนึ่งในกลุ่มที่คุณเลือก

คุณต้องการเพิ่มเส้นเชื่อมเพียงเส้นเดียวจาก $x$ ไปยัง $y$ ($1 \le x, y \le n$, $x \ne y$ และ $p_x = 0$ กล่าวคือคุณสามารถกำหนดให้ $p_x = y$) เพื่อให้คุณสามารถปรบมือบนกราฟทั้งหมดได้จำนวนครั้งมากกว่าเดิม อย่างไรก็ตาม การเพิ่มเส้นเชื่อมจะต้องไม่ทำให้เกิดวัฏจักรระบุทิศทางใดๆ ในกราฟ

จงหาเส้นเชื่อมดังกล่าวเส้นใดก็ได้ที่คุณสามารถเพิ่มได้ โดยการสอบถามจำนวนครั้งสูงสุดที่คุณสามารถปรบมือได้บนสับเซตของจุดยอดไม่เกิน $n$ สับเซต หรือระบุว่าเป็นไปไม่ได้ที่จะเพิ่มเส้นเชื่อมดังกล่าว

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $n$ ($1 \le n \le 1000$) เพียงตัวเดียว

การโต้ตอบ

ในการสอบถามแต่ละครั้ง ให้พิมพ์บรรทัดเดียวในรูปแบบ $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$ โดยที่ $1 \le k \le n$ และ $1 \le u_i \le n$ คือจุดยอดที่แตกต่างกันทั้งหมดในสับเซตที่คุณเลือก จากนั้นให้อ่านบรรทัดเดียวที่มีจำนวนเต็มหนึ่งตัว: จำนวนครั้งสูงสุดที่คุณสามารถปรบมือได้โดยที่หมากฮอสสามารถเริ่มต้นบนจุดยอดหนึ่งในกลุ่มที่คุณเลือกและจบลงบนจุดยอดหนึ่งในกลุ่มที่คุณเลือก คุณสามารถสอบถามได้ไม่เกิน $n$ ครั้ง

หลังจากที่คุณระบุเส้นเชื่อมที่คุณต้องการเพิ่มได้แล้ว ให้พิมพ์บรรทัดเดียวในรูปแบบ $\texttt{! } x \text{ } y$ โดยที่ $1 \le x, y \le n$ คือจุดปลายของเส้นเชื่อมระบุทิศทางที่คุณต้องการเพิ่ม หากมีคำตอบได้หลายแบบ คุณสามารถแสดงคำตอบใดก็ได้

หากเป็นไปไม่ได้ที่จะเพิ่มเส้นเชื่อมดังกล่าว ให้พิมพ์ $-1 \text{ -1}$ แทนจุดปลายของเส้นเชื่อม

โปรแกรมของคุณต้องหยุดทำงานทันทีหลังจากแสดงคำตอบแล้ว

ให้ล้างบัฟเฟอร์ข้อมูลส่งออก (flush) หลังจากการสอบถามแต่ละครั้ง

อินเทอร์แอกเตอร์ไม่ได้ปรับเปลี่ยนตามคำถาม (not adaptive); กราฟถูกกำหนดไว้ล่วงหน้าแล้ว

ตัวอย่าง

6

2

1

2
? 4 1 2 3 4

? 2 5 6

? 3 4 5 6

! 5 1

หมายเหตุ

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.