Mô tả bài toán
Đây là một bài toán tương tác. Trong tỉnh Plang, có $n = 300$ học sinh vừa tham gia Plang OI 2026. Trong số đó, một số bạn đã giành huy chương vàng, số còn lại thì không. Học sinh ở tỉnh Plang có một thói quen kỳ lạ. Nếu họ không giành được huy chương vàng, họ sẽ thành thật nói rằng họ không giành được. Tuy nhiên, nếu họ đã giành được, họ sẽ nói rằng họ đã giành được với xác suất $p$, còn lại với xác suất $1-p$ họ sẽ nói rằng họ không giành được. Lưu ý rằng mỗi câu trả lời là ngẫu nhiên và không liên quan đến câu trả lời trước đó. Bạn, với tư cách là huấn luyện viên của tỉnh Plang, muốn biết liệu mỗi học sinh có giành được huy chương vàng hay không. Sau đó, bạn có thể để Una thực hiện các hành động sau: * Chọn một số học sinh phân biệt và yêu cầu Una hỏi từng người trong số họ xem họ có giành được huy chương vàng hay không. Una sẽ cho bạn biết số người trả lời "Có".
Ngưỡng huy chương vàng của Plang OI 2025 là 571, vì vậy bạn nên tìm câu trả lời với số truy vấn trung bình không quá 568. Do những hạn chế của Plang OI, bạn có thể giả định rằng có chính xác 48 học sinh giành được huy chương vàng.
Hình 1: Một huấn luyện viên hỏi một học sinh xem có bao nhiêu điểm anh ta đã giấu.
Giao tiếp
Đây là một bài toán tương tác. Hãy nhớ làm sạch bộ đệm đầu ra sau mỗi lần in. Để làm sạch đầu ra của bạn, bạn có thể sử dụng:
fflush(stdout) hoặc cout.flush() trong C/C++;
System.out.flush() trong Java và Kotlin;
* sys.stdout.flush() trong Python.
Đầu tiên, bạn nên đọc một số nguyên $T$ ($T = 20$) cho biết số lượng trường hợp kiểm thử. Đối với mỗi trường hợp kiểm thử, bạn nên đọc một số nguyên $n$ ($n = 300$), cho biết số lượng học sinh. Để thực hiện một truy vấn, bạn nên in ra một dòng có định dạng "?k P1 P2... Pk" ($1 \le P_i \le n$, $P_i \ne P_j$ với $i \ne j$). Sau đó, đọc một số nguyên cho biết câu trả lời mà Una tìm thấy. Nếu truy vấn của bạn không hợp lệ, hoặc nếu bạn thực hiện hơn $568T$ truy vấn, chương trình giám khảo sẽ in ra -1. Sau khi đọc -1, bạn nên thoát ngay lập tức để tránh hành vi không xác định.
Nếu bạn nhận được câu trả lời, bạn nên in ra một dòng có định dạng "! $s_1 s_2 \dots s_n$", trong đó $s_i = 1$ cho biết học sinh thứ $i$ giành được huy chương vàng, $0$ nếu ngược lại. Sau đó, đọc một từ OK hoặc WA cho biết câu trả lời của bạn có đúng hay không. Nếu chương trình của bạn đọc được WA, bạn nên thoát ngay lập tức để tránh hành vi không xác định.
Lưu ý rằng giám khảo không thích ứng, nghĩa là câu trả lời sẽ không thay đổi sau các truy vấn của bạn. Có tối đa 10 bài kiểm thử.
Ví dụ
Dữ liệu vào 1
1 2 0 0 1 OK
Dữ liệu ra 1
?2 1 2 ?1 1 ?1 2 ! 01
Ghi chú
Lưu ý rằng ví dụ chỉ mang tính tham khảo, nó không thỏa mãn $T = 20$ và $n = 300$, và nó sẽ không xuất hiện trong các bài kiểm thử cuối cùng. Một công cụ kiểm thử được cung cấp để giúp các thí sinh phát triển và kiểm tra giải pháp của họ. Bạn có thể tải xuống công cụ này từ các tệp đính kèm. Thực thi công cụ với tùy chọn "-h" sẽ mô tả cách sử dụng công cụ. Công cụ kiểm thử sẽ chỉ triển khai một số kịch bản kiểm thử và chỉ một số chức năng của chương trình giám khảo thực tế.