Trong vườn thú có \(N\) con hải ly, đánh số từ \(0\) đến \(N-1\). Hải ly \(i\) thích táo có khối lượng trong đoạn \([L_i,R_i]\), nhưng bạn không biết các giá trị \(L_i,R_i\).

Bạn cần chọn đúng \(K\) con để đưa vào khu trưng bày. Hai con sẽ đánh nhau nếu hai khoảng sở thích của chúng giao nhau, tức tồn tại \(x\) thỏa \(L_i ≤ x ≤ R_i\) và \(L_j ≤ x ≤ R_j\). Đề bảo đảm tồn tại một cách chọn \(K\) con không đánh nhau.

Đây là bài tương tác. Bạn có thể hỏi không quá \(1000\) lần để tìm một tập hợp hợp lệ. Bộ chấm không thích nghi: mọi câu trả lời đã được cố định từ đầu.

Dữ liệu vào

Ban đầu, chương trình nhận một dòng chứa \(N\) và \(K\). Sau đó, chương trình nhận các câu trả lời của bộ chấm theo giao thức tương tác bên dưới.

Dữ liệu ra

Chương trình gửi các truy vấn và câu trả lời cuối cùng qua standard output theo giao thức tương tác bên dưới. Phải flush sau mỗi lần xuất.

Giao thức tương tác

Ban đầu, chương trình nhận một dòng gồm $N$ và $K$.

Để hỏi về tập các chỉ số phân biệt \(t_0,t_1,...,t_{m-1}\), in và flush:

? m t0 t1 ... t(m-1)

trong đó \(0 ≤ m ≤ N\) và mọi \(t_i\) thuộc \([0,N-1]\). Sau đó đọc số nguyên \(r\): số hải ly lớn nhất có thể chọn từ tập vừa hỏi mà không đánh nhau. Giá trị \(r\) có thể lớn hơn \(K\). Nếu nhận -1, phải kết thúc ngay.

Để trả lời, in và flush đúng một lần:

! s0 s1 ... s(K-1)

Các \(s_i\) phải là \(K\) chỉ số phân biệt trong \([0,N-1]\), và các khoảng sở thích tương ứng không được giao nhau. Mọi định dạng khác đều bị từ chối.

Ràng buộc

• \(1 ≤ N ≤ 1000\).
• \(1 ≤ K ≤ min(10,N)\).
• \(1 ≤ L_i ≤ R_i ≤ 10000\).
• Có ít nhất một cách chọn \(K\) hải ly không đánh nhau.
• Không được dùng quá \(1000\) truy vấn.

Phân nhóm

1. \(6\) điểm: \(N ≤ 8\).
2. \(7\) điểm: \(N ≤ 12\).
3. \(14\) điểm: \(N ≤ 20\).
4. \(21\) điểm: \(N ≤ 50\).
5. \(16\) điểm: \(N ≤ 90\).
6. \(36\) điểm: không có ràng buộc thêm. Nếu mọi test của phân nhóm này đúng, đặt \(T\) là số truy vấn lớn nhất: nhận \(13\) điểm khi \(100<T ≤ 1000\), và \(36\) điểm khi \(T ≤ 100\).

Ví dụ

4 2
2 6
3 6
4 10
8 11

Judge: 4 2
User:  ? 2 0 2
Judge: 1
User:  ? 1 1
Judge: 1
User:  ? 3 3 2 1
Judge: 2
User:  ! 1 3

L_i,R_i trong ví dụ chỉ là input của testing tool; chương trình nộp bài chỉ nhận $N$ và $K$ từ judge.

Nguồn

JOIG 2025/2026 - Chung kết, Cuộc thi 2, bài Zoo.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.