KOI TST 2026 - Sorting

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
C++
Điểm: 2800 (p) Thời gian: 5.0s Bộ nhớ: 2G Input: bàn phím Output: màn hình

Đề bài

Alice có \(N\) đồ vật, đánh số từ \(0\) đến \(N-1\). Giá trị của vật \(i\) là một số nguyên không âm \(A[i]\). Alice biết toàn bộ giá trị, còn Bob chỉ biết \(N\) và biết rằng các giá trị không âm.

Bob cần trả về một hoán vị \(P\) sao cho

\[ A[P[i]]\le A[P[i+1]]\qquad(0\le i<N-1). \]

Bob có thể hỏi Alice không quá \(10\,000\) lần. Trong mỗi câu hỏi:

  1. Bob nối các đồ vật bằng đúng \(N-1\) sợi dây, mỗi dây nối hai đồ vật phân biệt, sao cho mọi cặp đồ vật đều liên thông qua các sợi dây. Nói cách khác, các dây tạo thành một cây.
  2. Alice chọn một tập đồ vật độc lập trên cây: không có hai vật được chọn nối trực tiếp với nhau. Tổng giá trị các vật được chọn phải lớn nhất có thể.
  3. Nếu có nhiều tập tối ưu, Alice tùy ý trả về một trong số đó. Sau đó các dây được tháo bỏ.

Hãy giúp Bob sắp xếp các đồ vật với ít câu hỏi nhất.

Yêu cầu cài đặt

C++
vector<int> sorting(int N);
vector<int> ask_question(vector<array<int, 2>> threads);
  • sorting(N) được gọi đúng một lần và phải trả về một hoán vị \(P\) sắp theo giá trị không giảm. Nếu có nhiều đáp án, có thể trả về bất kỳ đáp án hợp lệ nào.
  • ask_question(threads) thực hiện một câu hỏi. threads phải chứa đúng \(N-1\) cạnh và tạo thành một cây liên thông trên các đỉnh \(0,\ldots,N-1\).
  • Hàm trả về mảng nhị phân \(C\) độ dài \(N\), với \(C[i]=1\) khi Alice chọn vật \(i\).
  • Cùng một mảng threads có thể nhận các đáp án tối ưu khác nhau ở những lần gọi khác nhau.
  • ask_question được gọi nhiều nhất \(10\,000\) lần trong một test.
  • Chương trình nộp không được thực hiện thao tác vào/ra.

Ràng buộc

  • \(5\le N\le 1\,000\).
  • \(A[i]\) là số nguyên không âm và không có cận trên được công bố.
  • Grader có tính thích nghi: mảng \(A\) không nhất thiết được cố định trước. Sau mỗi câu trả lời, luôn tồn tại ít nhất một mảng \(A\) phù hợp với toàn bộ câu trả lời trước đó.
  • Có thể giả sử phần grader xử lý các câu hỏi trong không quá \(2\) giây và dùng không quá \(16\) MiB cho mỗi test, không tính tài nguyên của bài nộp.

Phân nhóm

Nhóm Điểm Ràng buộc bổ sung
1 7 \(N=5\).
2 8 \(N\le 100\).
3 10 Có nhiều nhất một chỉ số \(i\) thỏa mãn \(A[i]>0\).
4 30 \(A[i]=0\) với mọi \(0\le i<N/2\).
5 45 Không có ràng buộc bổ sung.

Ở nhóm 1 và 2, đáp án đúng nhận toàn bộ điểm nhóm. Ở nhóm 3, 4 và 5, bài sai hoặc kết thúc bất thường nhận \(0\) điểm. Nếu đáp án đúng, gọi \(Q_{\max}\) là số câu hỏi lớn nhất trong một lần chạy thuộc nhóm và xác định \(X\) như sau:

\[ X= \begin{cases} 0, & Q_{\max}>10\,000,\\ 90-35\log_{10}\left(\dfrac{Q_{\max}}{80}\right), & 80<Q_{\max}\le 10\,000,\\ 170-Q_{\max}, & 70<Q_{\max}\le 80,\\ 100, & Q_{\max}\le 70. \end{cases} \]

Điểm nhận được bằng \(X\%\) số điểm của nhóm.

Grader mẫu

Grader mẫu đọc \(N\) và mảng \(A\). Grader in hoán vị do sorting trả về trên dòng đầu và số lần gọi ask_question trên dòng thứ hai. Grader mẫu chỉ được đảm bảo hoạt động khi \(0\le A[i]\le 10^9\) và có thể khác grader chính thức.

Ví dụ

Input 
6
5 3 3 0 8 1
Output 
3 5 1 2 0 4
2

Vì hai vật \(1\) và \(2\) có cùng giá trị, hoán vị 3 5 2 1 0 4 cũng hợp lệ.

Nguồn: Kỳ thi tuyển chọn đội tuyển IOI Hàn Quốc 2026 - Vòng 2, giấy phép CC BY-NC-SA 4.0.

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: