Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 インタラクティブ
統計

Mô tả

Có một đồ thị có hướng gồm $n$ đỉnh được đánh số từ $1$ đến $n$. Với mỗi đỉnh $1 \le i \le n$, bậc ra của đỉnh $i$ nhiều nhất là một; do đó ta có thể mô tả đồ thị bằng một mảng $p_i$, trong đó $p_i = 0$ nếu bậc ra của đỉnh $i$ bằng không, và ngược lại $1 \le p_i \le n$, $p_i \ne i$, đồng thời có một cạnh có hướng từ $i$ đến $p_i$. Không có chu trình có hướng nào trong đồ thị, vì vậy từ bất kỳ đỉnh $i$ nào, đường đi tạo bởi việc liên tục di chuyển sang đỉnh tiếp theo dọc theo các cạnh có hướng cuối cùng sẽ kết thúc tại một đỉnh có bậc ra bằng không.

Ban đầu, có một quân cờ bằng gỗ nằm trên một trong các đỉnh. Khi bạn vỗ tay, nếu quân cờ đang ở một đỉnh $i$ có $p_i$ khác không, nó sẽ di chuyển đến đỉnh $p_i$; ngược lại nó đứng yên. Tuy nhiên, bạn hoàn toàn không thể nhìn thấy quân cờ đang ở đâu — thao tác duy nhất bạn có thể thực hiện là chọn một tập con các đỉnh, đặt quân cờ lên một trong các đỉnh đã chọn, vỗ tay một số lần, và quan sát xem liệu quân cờ có kết thúc tại một trong các đỉnh bạn đã chọn hay không. Thậm chí vị trí đặt quân cờ ban đầu và số lần bạn vỗ tay cũng do trình tương tác chọn: bạn chỉ được chọn tập con các đỉnh, và quan sát số lần tối đa bạn có thể vỗ tay sao cho quân cờ có thể bắt đầu ở một trong các đỉnh đã chọn và kết thúc ở một trong các đỉnh đã chọn.

Bạn muốn thêm một cạnh duy nhất từ $x$ đến $y$ ($1 \le x, y \le n$, $x \ne y$, và $p_x = 0$, tức là bạn có thể gán $p_x = y$), sao cho bạn có thể vỗ tay nhiều lần hơn trước trên toàn bộ đồ thị. Tuy nhiên, việc thêm cạnh này không được tạo ra bất kỳ chu trình có hướng nào trong đồ thị.

Hãy tìm một cạnh bất kỳ như vậy mà bạn có thể thêm bằng cách truy vấn số lần vỗ tay tối đa trên nhiều nhất $n$ tập con các đỉnh, hoặc xác định rằng không thể thêm một cạnh như vậy.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $n$ ($1 \le n \le 1000$).

Tương tác

Để thực hiện một truy vấn, hãy in ra một dòng có dạng $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, trong đó $1 \le k \le n$, và $1 \le u_i \le n$ là các đỉnh đôi một phân biệt trong tập con bạn chọn. Sau đó đọc một dòng chứa một số nguyên duy nhất: số lần tối đa bạn có thể vỗ tay sao cho quân cờ có thể bắt đầu ở một trong các đỉnh đã chọn và kết thúc ở một trong các đỉnh đã chọn. Bạn được thực hiện nhiều nhất $n$ truy vấn.

Sau khi đã xác định được cạnh muốn thêm, hãy in ra một dòng có dạng $\texttt{! } x \text{ } y$, trong đó $1 \le x, y \le n$ là hai đầu mút của cạnh có hướng bạn muốn thêm. Nếu có nhiều đáp án, bạn có thể in ra bất kỳ đáp án nào.

Nếu không thể thêm được cạnh như vậy, hãy in ra $-1 \text{ -1}$ thay vì hai đầu mút của cạnh.

Chương trình của bạn phải kết thúc ngay lập tức sau khi in ra đáp án.

Hãy xóa bộ đệm xuất (flush) sau mỗi truy vấn bạn thực hiện.

Trình tương tác không thích ứng (non-adaptive); đồ thị đã được cố định trước.

Ví dụ

6

2

1

2
? 4 1 2 3 4

? 2 5 6

? 3 4 5 6

! 5 1

Ghi chú

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.