Universal Cup Judging System

Universal Cup

時間限制: 2.0 s 記憶體限制: 1024 MB 總分: 100 难度: [顯示] 互動 可 Hack ✓
统计

תיאור הבעיה

כמובן, זו בעיה.

זוהי בעיה אינטראקטיבית. נתון לך גרף לא מכוון ולא ידוע עם $n$ צמתים ו-$m$ קשתות, ללא קשתות מקבילות או לולאות עצמיות. בכל פעם, תוכל לשאול את ספריית האינטראקציה את השאלה הבאה:

  • בהינתן קבוצת צמתים $S \subseteq \{1, 2, \dots, n\}$, שאל האם קבוצת צמתים זו היא קבוצה בלתי תלויה.

כאן, קבוצה בלתי תלויה משמעותה שאין קשת בין אף שני צמתים שונים בקבוצה $S$.

המטרה שלך היא לקבוע את כל קבוצת הקשתות של הגרף באמצעות לא יותר מ-$M = n + m(2 + \lceil\log_2 n\rceil)$ שאילתות.

שים לב שאינך יודע את ערכו של $m$ מראש, וספריית האינטראקציה היא אדפטיבית, כלומר הגרף אינו קבוע מההתחלה, אלא יותאם באופן דינמי בהתאם לשאילתות שלך.

קלט

השורה הראשונה מכילה מספר שלם $T$ ($1 \le T \le 100$), המציין את מספר מקרי הבדיקה.

עבור כל מקרה בדיקה, שורה אחת מכילה מספר שלם $n$ ($1 \le n \le 500$), המציין את מספר הצמתים של הגרף הלא מכוון הלא ידוע.

מובטח כי סכום ערכי ה-$n$ על פני כל מקרי הבדיקה אינו עולה על $500$, $0 \le m \le 500$, וסכום ערכי ה-$m$ אינו עולה על $500$.

אינטראקציה

כאשר ברצונך לבצע שאילתה, הדפס שורה אחת:

? k v_1 v_2 ... v_k

כאשר $k$ מציין את גודל קבוצת הצמתים, ו-$v_1, v_2, \dots, v_k$ הם האינדקסים של הצמתים בקבוצה שעליה אתה שואל, כולם שונים זה מזה.

ספריית האינטראקציה תחזיר מספר שלם: $1$ אם קבוצת הצמתים היא קבוצה בלתי תלויה; $0$ אחרת.

כאשר קבעת את כל קשתות הגרף, הדפס שורה אחת:

! m u_1 v_1 u_2 v_2 ... u_m v_m

כאשר $m$ הוא מספר הקשתות בגרף הלא מכוון, ו-$(u_i, v_i)$ מייצג קשת בגרף. ניתן להדפיס את הקשתות בכל סדר.

לאחר מכן, אם לא נותרו מקרי בדיקה נוספים, על התוכנית שלך להסתיים מיד; אחרת, עליה להמשיך למקרה הבדיקה הבא.

דוגמאות

קלט 1

1
4
0
1
0
0
1
0

פלט 1

? 2 1 2
? 2 1 3
? 2 1 4
? 2 2 3
? 2 2 4
? 2 3 4
! 4 1 2 2 3 3 4 1 4

הערה

הדוגמה מדגימה תהליך אינטראקטיבי של שאילתה לגבי קיומה של כל קשת בנפרד.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1842EditorialOpenNew Editorial for Problem #18123wangmaruiView

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.