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

תיאור

נתון גרף מכוון עם $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) לאחר כל שאילתה שאתה מבצע.

האינטראקטור אינו אדפטיבי; הגרף קבוע מראש.

דוגמה

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.