Có nhiều truyền thuyết về tháp nghiêng Toruń. Bức tường của tháp có dạng một đường tròn với \(n \ge 3\) cánh cửa cách đều nhau, tức là các cánh cửa nằm tại các đỉnh của một đa giác đều \(n\) cạnh. Các cửa được đánh số từ \(0\) đến \(n-1\) theo một thứ tự ngẫu nhiên. Cách chọn thứ tự này được mô tả trong phần Phân nhóm.

Một truyền thuyết ít người biết kể rằng mỗi cư dân mới của tháp đều phải vượt qua một thử thách: liệt kê các cánh cửa, bắt đầu từ một cửa bất kỳ rồi đi một vòng theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, ghé qua mỗi cửa đúng một lần.

Thử thách phải được hoàn thành mà không được nhìn thấy tháp. Thay vào đó, cư dân mới có thể đặt câu hỏi như sau: “Với ba cửa phân biệt \(x\), \(y\), \(z\), những cặp cửa nào trong ba cặp \(\{x,y\}\), \(\{y,z\}\) và \(\{z,x\}\) gần nhau nhất?”. Câu trả lời gồm tất cả các cặp trong ba cặp trên có khoảng cách Euclid nhỏ nhất. Khoảng cách giữa hai cửa là độ dài đoạn thẳng ngắn nhất nối chúng.

Hãy viết chương trình sử dụng ít câu hỏi để xác định thứ tự các cửa.

Cài đặt

Bản chuyển đổi này sử dụng giao diện hàm C++. Nộp một tệp C++17 hoặc C++20, thêm #include "tower.h" và cài đặt hai hàm sau. Tệp khai báo tower.h được cung cấp trong phần đính kèm.

void Init(int T, int K);
void Solve(int n);

Trình chấm gọi Init(T, K) đúng một lần khi bắt đầu bài kiểm tra: T là số bộ dữ liệu và K là số truy vấn trung bình tối đa. Sau đó trình chấm gọi Solve(n) đúng T lần, theo thứ tự bộ dữ liệu. Mỗi lần gọi tương ứng với một tháp mới có n cửa; biến toàn cục của chương trình vẫn được giữ giữa các lần gọi. Trong phần còn lại của đề, \(t=T\) và \(k=K\).

Trong Solve, bạn được sử dụng hai hàm do trình chấm cung cấp:

std::vector<std::pair<int, int>> Query(int x, int y, int z);
void Answer(const std::vector<int>& order);

• Query(x, y, z) đặt một câu hỏi về ba cửa phân biệt thuộc đoạn \([0,n-1]\) và trả về tất cả các cặp có khoảng cách nhỏ nhất. Kết quả có từ \(1\) đến \(3\) cặp; mỗi cặp (a, b) thỏa mãn a < b. Không được giả định thứ tự của các cặp trong kết quả. Mỗi lần gọi tính là một truy vấn, kể cả truy vấn lặp lại.
• Answer(order) gửi một hoán vị gồm đúng n số nguyên, mô tả thứ tự các cửa khi đi một vòng quanh tháp. Mọi phép quay và đảo chiều của thứ tự đúng đều được chấp nhận, tổng cộng \(2n\) đáp án đúng. Phải gọi Answer đúng một lần trong mỗi lần gọi Solve, rồi trả về từ Solve. Không được gọi Query hoặc Answer thêm sau khi đã gửi đáp án.

Không gọi Query hoặc Answer trong Init hay bên ngoài Solve. Không cài đặt main, không đọc đầu vào chuẩn, không ghi đầu ra chuẩn, không mở tệp hoặc truy cập tài nguyên khác. Có thể ghi vào luồng lỗi chuẩn để gỡ lỗi; thời gian ghi vẫn được tính. Trình chấm chịu trách nhiệm đọc dữ liệu và xuất kết quả.

Trả về mà chưa gửi đáp án, gửi đáp án sai, gọi hàm sai quy định hoặc vượt tổng số truy vấn \(T\cdot K\) đều làm cả phân nhóm nhận \(0\) điểm. Giới hạn truy vấn áp dụng cho tổng của bài kiểm tra, không phải riêng từng tháp. Thứ tự các cửa đã được cố định từ trước và không thay đổi theo các truy vấn.

Ràng buộc

• \(1 \le t \le 100\).
• \(1 \le k \le 12\,000\).
• \(3 \le n \le 500\).
• Trong mỗi truy vấn, \(0 \le x,y,z \le n-1\) và ba giá trị này đôi một khác nhau.

Phân nhóm

Mỗi phân nhóm có đúng một bài kiểm tra gồm đúng \(t=100\) bộ dữ liệu. Số truy vấn trung bình của một bài kiểm tra được tính bằng tổng số truy vấn trên tất cả các bộ dữ liệu chia cho số bộ dữ liệu. Nếu giá trị trung bình này lớn hơn \(k\) của phân nhóm, bạn nhận \(0\) điểm cho phân nhóm đó. Nếu không vượt quá \(k\), bạn nhận toàn bộ điểm của các phân nhóm từ \(1\) đến \(4\).

Với phân nhóm cuối cùng, gọi \(k^*\) là số truy vấn trung bình thực tế mà chương trình sử dụng. Khi không vượt quá giới hạn truy vấn, số điểm được tính bằng:

Biểu thức bên trong dấu làm tròn tăng tuyến tính từ \(0\) đến \(56\) khi \(k^*\) giảm từ \(12000\) xuống \(4200\); số điểm được làm tròn lên đến số nguyên gần nhất.

Nếu chương trình đưa ra đáp án sai ở bất kỳ bộ dữ liệu nào, bạn nhận \(0\) điểm cho cả phân nhóm đó, bất kể số truy vấn đã sử dụng.

1. \(6\) điểm: \(k=8000\) và \(3 \le n \le 9\).
2. \(7\) điểm: \(k=4500\) và \(40 \le n \le 50\).
3. \(9\) điểm: \(k=3000\) và \(90 \le n \le 100\).
4. \(22\) điểm: \(k=4500\), \(n=400\), và tồn tại một đáp án đúng \(x_0, \ldots, x_{n-1}\) thỏa mãn \(x_i=i\) với mọi \(200 \le i \le 399\).
5. Tối đa \(56\) điểm: \(k=12\,000\) và \(n=500\).

Mỗi bộ dữ liệu được sinh bằng cách chọn \(n\) ngẫu nhiên đều trong tất cả các giá trị thỏa mãn ràng buộc của phân nhóm, rồi chọn thứ tự các cửa ngẫu nhiên đều trong tất cả các thứ tự của \(n\) cửa thỏa mãn ràng buộc của phân nhóm đó.

Ví dụ

Giả sử có một bộ dữ liệu với \(n=6\) và thứ tự các cửa là \(5,3,0,2,1,4\). Một chuỗi lời gọi hợp lệ là:

Đây là minh họa giao diện, không phải thuật toán suy ra đáp án chỉ từ ba truy vấn này. Ví dụ có \(t=1\); mỗi bài kiểm tra tính điểm chính thức có \(t=100\).

Ở hình bên trái, các cửa \(0\), \(1\), \(2\) tương ứng với truy vấn đầu tiên; hai cặp \(\{0,2\}\) và \(\{1,2\}\) có khoảng cách nhỏ nhất. Ở hình giữa, cặp \(\{1,4\}\) có khoảng cách nhỏ nhất trong ba cửa \(4\), \(1\), \(3\). Ở hình bên phải, cả ba cặp giữa các cửa \(0\), \(5\), \(1\) đều có cùng khoảng cách.

Các dãy \(0,2,1,4,5,3\) hoặc \(5,4,1,2,0,3\) cũng là đáp án đúng.