Phù! Sau màn ra mắt thảm họa với tư cách một tên trộm tác phẩm nghệ thuật, bạn vừa thoát khỏi nhà tù trong gang tấc. Có lẽ bước vào giới nghệ thuật bằng con đường hợp pháp vẫn hơn. Vì thế, bạn quyết định làm nhà phê bình nghệ thuật tại chính bảo tàng nơi mình từng bị bắt.
Bạn sẽ đến bảo tàng nhiều lần và viết một bài đánh giá sau mỗi lần ghé thăm. Mỗi bài đánh giá xem xét một số cặp phòng. Với mỗi cặp, bạn so sánh các tác phẩm trong hai phòng trong lần ghé thăm đó và xác định phòng nào trưng bày bộ sưu tập có giá trị thẩm mỹ cao hơn. Tất nhiên, đánh giá nghệ thuật chỉ có tính tương đối: sau mỗi lần ghé thăm, bạn chỉ biết thứ tự tương đối trong từng cặp đã so sánh, chứ không biết thứ tự giữa những phòng thuộc các cặp khác nhau. Cuối cùng, bạn còn muốn tổng kết toàn bộ nghệ thuật trong bảo tàng: dùng tất cả các bài đánh giá để xếp hạng mọi phòng theo giá trị thẩm mỹ giảm dần của bộ sưu tập đang được trưng bày.
Vì việc lên kế hoạch rất quan trọng, trước mỗi lần ghé thăm, bạn quyết định sẵn những cặp phòng sẽ so sánh. Để bảo đảm sự đa dạng, mỗi phòng không được xuất hiện quá một lần trong cùng một bài đánh giá.
Không may, danh tiếng mới của bạn trong giới nghệ thuật lại gây trở ngại. Mỗi khi bạn thông báo rằng sẽ so sánh một cặp phòng cụ thể trong lần ghé thăm tiếp theo, bảo tàng có thể bất ngờ đổi chỗ hai bộ sưu tập của hai phòng đó. Bản tổng kết và thứ hạng cuối cùng phải dựa trên những gì được trưng bày trong từng phòng vào lần ghé thăm cuối cùng của bạn.
Hãy viết chương trình lên lịch không quá \(V\) lần ghé thăm, rồi dựa vào các kết quả so sánh để lập danh sách tất cả các phòng theo giá trị thẩm mỹ giảm dần của bộ sưu tập trong từng phòng tại lần ghé thăm cuối cùng.
Giao tiếp
Đây là bài toán giao tiếp. Bạn phải cài đặt hàm sau:
C++void solve(int N, int V);
\(N\) là số phòng của bảo tàng, được đánh số từ \(1\) đến \(N\), còn \(V\) là số lần ghé thăm tối đa được phép thực hiện. Với mỗi bộ dữ liệu, hàm này được gọi đúng một lần. Bạn có thể gọi các hàm sau do trình chấm cung cấp:
C++void schedule(int i, int j);
std::vector<int> visit();
void answer(std::vector<int> r);
schedule(i, j) lên lịch so sánh phòng \(i\) và phòng \(j\) trong lần ghé thăm tiếp theo, với \(1\le i,j\le N\) và \(i\ne j\). Ngay sau lời gọi này, bảo tàng có thể quyết định đổi chỗ các bộ sưu tập của phòng \(i\) và phòng \(j\).visit() ghé thăm bảo tàng và thực hiện tất cả các phép so sánh đã lên lịch. Hàm trả về một mảng có đúng một phần tử cho mỗi phép so sánh được lên lịch kể từ lần ghé thăm trước, tức là cho mỗi lời gọi schedule kể từ lời gọi visit gần nhất hoặc từ khi chương trình bắt đầu. Phần tử ở chỉ số \(k\) bằng \(1\) nếu bộ sưu tập trong phòng \(i\) có giá trị thẩm mỹ cao hơn trong phòng \(j\), và bằng \(0\) trong trường hợp còn lại; ở đây, \(i,j\) là cặp phòng trong phép so sánh thứ \(k+1\) được lên lịch. Chỉ số mảng bắt đầu từ \(0\).answer(r) công bố danh sách tất cả các phòng theo giá trị thẩm mỹ giảm dần. Mảng \(r\) phải có độ dài \(N\); phần tử ở chỉ số \(i\) là phòng có bộ sưu tập đứng thứ \(i+1\) về giá trị thẩm mỹ trong lần ghé thăm cuối cùng. Bạn phải gọi answer đúng một lần; chương trình tự động kết thúc sau lời gọi này.
Nếu một lời gọi hàm không đúng định dạng trên, nếu một phòng xuất hiện nhiều hơn một lần trong các tham số truyền cho schedule giữa hai lần gọi visit (hoặc từ khi chương trình bắt đầu đến lần gọi visit đầu tiên), hoặc nếu gọi visit quá \(V\) lần, chương trình lập tức bị kết thúc và nhận kết quả Not correct cho bộ dữ liệu đó. Không được ghi bất kỳ thứ gì ra đầu ra chuẩn; nếu vi phạm, bạn có thể nhận kết quả Security violation!.
Nếu dùng C++, mã nguồn phải có #include "swaps.h". Để chạy thử trên máy, bạn có thể liên kết chương trình với sample_grader.cpp, được cung cấp trong phần đính kèm của bài trên CMS chính thức. Phần đính kèm còn có tệp cài đặt mẫu swaps_sample.cpp với các giải thích bổ sung. Nếu dùng Python, tệp mẫu swaps_sample.py trong phần đính kèm mô tả giao diện dành cho bài nộp Python.
Dữ liệu vào
Bài nộp nhận \(N\) và \(V\) qua tham số của solve, rồi nhận các kết quả so sánh qua giá trị trả về của visit.
Trình chấm mẫu nhận từ đầu vào chuẩn hai số \(N\), \(V\) cùng một danh sách \(N\) số nguyên là các phòng theo giá trị thẩm mỹ giảm dần ở thời điểm bắt đầu solve. Mỗi khi chương trình gọi schedule(i, j), trình chấm mẫu tiếp tục đọc một số từ đầu vào chuẩn: \(1\) nếu cần đổi chỗ các bộ sưu tập của phòng \(i\) và phòng \(j\) ngay lúc đó, hoặc \(0\) nếu không đổi.
Dữ liệu ra
Bài nộp trả lời bằng answer, không ghi ra đầu ra chuẩn. Trình chấm mẫu ghi nhật ký tất cả các lời gọi hàm ra đầu ra chuẩn và kết thúc bằng một trong các thông báo ở phần “Trình chấm mẫu”.
Ràng buộc
- \(1\le N\le500\).
- \(50\le V\le5\,000\).
- Mỗi phòng xuất hiện nhiều nhất một lần trong các phép so sánh của một lần ghé thăm.
Phân nhóm
- \(5\) điểm: \(V=5\,000\) và bảo tàng không bao giờ đổi chỗ các bộ sưu tập.
- \(10\) điểm: \(V\ge1\,000\) và bảo tàng không bao giờ đổi chỗ các bộ sưu tập.
- \(5\) điểm: \(N\le100\), \(V=5\,000\).
- \(15\) điểm: \(V=5\,000\).
- \(15\) điểm: \(V\ge500\).
- \(35\) điểm: \(V\ge100\).
- \(15\) điểm: \(V\ge50\).
Trong mỗi phân nhóm từ \(3\) đến \(7\), bạn nhận được \(60\%\) số điểm của phân nhóm nếu giải đúng tất cả các bộ dữ liệu mà với mỗi lời gọi schedule(i, j), bảo tàng luôn đặt bộ sưu tập có giá trị thẩm mỹ cao hơn vào phòng \(i\). Trên CMS, các bộ dữ liệu này được hiển thị là “Group 1” của phân nhóm tương ứng.
Ví dụ giao tiếp
Xét một bộ dữ liệu có \(N=4\) và \(V=50\), trong đó ban đầu các phòng được xếp theo giá trị thẩm mỹ giảm dần là \(1,2,3,4\). Trình chấm bắt đầu bằng lời gọi solve(4, 50). Một quá trình giao tiếp có thể diễn ra như sau; ký hiệu -> biểu diễn giá trị trả về, không phải dữ liệu bài nộp cần in:
schedule(1, 2)
schedule(3, 4)
visit() -> {1, 0}
schedule(2, 4)
visit() -> {1}
answer({1, 2, 4, 3})
Lời gọi đầu tiên lên lịch so sánh phòng \(1\) và phòng \(2\). Lời gọi thứ hai lên lịch so sánh phòng \(3\) và phòng \(4\); sau lời gọi này, bảo tàng đổi chỗ các bộ sưu tập trong phòng \(3\) và phòng \(4\). Lần gọi visit() đầu tiên thực hiện cả hai phép so sánh: bộ sưu tập trong phòng \(1\) có giá trị thẩm mỹ cao hơn phòng \(2\), còn bộ sưu tập trong phòng \(4\) cao hơn phòng \(3\).
Tiếp theo, bạn lên lịch so sánh phòng \(2\) và phòng \(4\). Lần ghé thăm thứ hai cho biết bộ sưu tập trong phòng \(2\) có giá trị thẩm mỹ cao hơn phòng \(4\). Bạn tin rằng thứ tự giảm dần là \(1,2,4,3\) và trả lời như vậy. Đáp án này đúng và được chấp nhận.
Tuy nhiên, các truy vấn trên chưa đủ để xác định chắc chắn thứ tự các phòng. Chẳng hạn, thứ tự \(2,1,4,3\) cũng phù hợp với mọi giá trị trả về của visit. Thứ tự này có thể xuất hiện nếu ban đầu thứ tự là \(4,1,2,3\) và bảo tàng đổi chỗ các bộ sưu tập trong phòng \(2\) và phòng \(4\) sau lời gọi schedule cuối cùng.
Trình chấm mẫu
Các thông báo kết thúc có ý nghĩa như sau:
Invalid input.: dữ liệu đưa vào trình chấm qua đầu vào chuẩn không đúng định dạng đã mô tả.Invalid schedule.: schedule được gọi với tham số không hợp lệ.Out of visits.: visit được gọi quá \(V\) lần.Invalid answer.: answer được gọi với tham số không hợp lệ.Wrong answer.: answer được gọi với một danh sách phòng không đúng.No answer.: solve kết thúc mà không gọi answer.Correct: v visit(s) used.: không xảy ra trường hợp nào ở trên và visit được gọi \(v\) lần.
Trình chấm dùng để đánh giá bài nộp chính thức chỉ đưa ra Not correct khi có lỗi hoặc Correct khi đúng. Cả trình chấm mẫu và trình chấm chính thức đều tự động kết thúc chương trình khi xảy ra một lỗi đã nêu hoặc khi chương trình gọi answer.
Giới hạn
Thời gian: \(1{,}5\) giây. Bộ nhớ: \(512\) MiB.
