Median Sort

Bạn muốn sắp xếp \(N\) phần tử phân biệt \(x_1,x_2,\ldots,x_N\). Không may, bạn không thể so sánh hai phần tử; với ba phần tử, bạn chỉ có thể hỏi phần tử nào là trung vị, tức không nhỏ nhất cũng không lớn nhất.

Ví dụ, với \(N=5\), biết \(x_1\) là trung vị của \(\{x_1,x_2,x_3\}\), \(x_2\) là trung vị của \(\{x_2,x_3,x_4\}\) và \(x_3\) là trung vị của \(\{x_3,x_4,x_5\}\) thì thứ tự được bảo đảm là \(x_4,x_2,x_1,x_3,x_5\) hoặc thứ tự đảo \(x_5,x_3,x_1,x_2,x_4\).

Chỉ từ trung vị, không thể phân biệt một thứ tự với thứ tự đảo của nó vì mọi truy vấn ba phần tử cho cùng kết quả trong cả hai.

Chương trình phải tìm thứ tự của \(T\) danh sách, mỗi danh sách có \(N\) phần tử, bằng tổng không quá \(Q\) truy vấn (trung bình \(Q/T\) mỗi danh sách). Thứ tự đúng hoặc đảo của nó đều được chấp nhận. Thứ tự mỗi bộ được sinh đều ngẫu nhiên trong mọi hoán vị, độc lập với mọi thông tin khác.

Giao thức tương tác

Các mục Dữ liệu vào và Dữ liệu ra dưới đây quy định đầy đủ cuộc đối thoại giữa chương trình và bộ chấm.

Dữ liệu vào

Đây là bài tương tác. Ban đầu bộ chấm gửi một dòng \(T,N,Q\). Sau đó xử lý \(T\) bộ; mỗi bộ gồm các lượt hỏi và một lượt trả lời.

Dữ liệu ra

Để hỏi, in ba số nguyên phân biệt \(i,j,k\) trong \([1,N]\), nghĩa là hỏi trung vị của \(\{x_i,x_j,x_k\}\). Bộ chấm trả một số \(L\in\{i,j,k\}\), nghĩa là \(x_L\) là trung vị. Nếu thực hiện truy vấn thứ \(Q+1\), bộ chấm trả -1.

Khi sẵn sàng, in \(N\) chỉ số theo thứ tự tăng hoặc giảm. Bộ chấm trả 1 nếu đúng, -1 nếu sai. Sau phản hồi của bộ thứ \(T\), chương trình phải kết thúc và không in thêm gì; nếu in thêm sẽ bị Wrong Answer.

Nếu bộ chấm nhận dòng sai định dạng hoặc giá trị không hợp lệ, nó trả -1 và không xuất thêm. Sau mọi -1, chương trình phải thoát ngay; tiếp tục chờ sẽ bị treo. Hãy xả bộ đệm sau mỗi dòng.

Ràng buộc

• \(T=100\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(N=10\), \(Q=300T\).
• Test Set 2 (Visible Verdict): \(N=50\), \(Q=300T\).
• Test Set 3 (Hidden Verdict): \(N=50\), \(Q=170T\).

Công cụ kiểm thử

Kho chính thức cung cấp công cụ mô phỏng để chạy cục bộ song song với lời giải qua interactive runner; hướng dẫn nằm trong chú thích của công cụ và người dùng được khuyến khích thêm bộ dữ liệu. Công cụ không phải bộ chấm thật và có thể hành xử khác; vượt qua nó không bảo đảm vượt bộ chấm. Bản LQDOJ dùng interactor đi kèm gói bài.

Ví dụ

Nguồn

Google Code Jam 2021, Vòng loại, bài Median Sort.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.