Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 1024 MB 총점: 100 인터랙티브
통계

الوصف

يوجد رسم بياني موجه يحتوي على $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$؛ وإلا فإنها لا تتحرك. ومع ذلك، لا يمكنك رؤية مكان القطعة على الإطلاق — العملية الوحيدة التي يمكنك إجراؤها هي اختيار مجموعة جزئية من الرؤوس، ووضع القطعة على أحد الرؤوس المختارة، والتصفيق بيديك عدداً من المرات، وملاحظة ما إذا كانت القطعة ستنتهي على أحد الرؤوس التي اخترتها. حتى الموضع الابتدائي للقطعة وعدد مرات التصفيق يتم اختيارهما بواسطة المتفاعل (interactor): يمكنك فقط اختيار المجموعة الجزئية من الرؤوس، وملاحظة أقصى عدد من المرات التي يمكنك فيها التصفيق بيديك بحيث تتمكن القطعة من البدء على أحد الرؤوس المختارة والانتهاء على أحد الرؤوس المختارة.

ترغب في إضافة حافة واحدة من $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.