USACO 2024 January Contest, Silver, Cowmpetency
Xem PDFNông dân John đang tuyển thêm bò đầu đàn cho đàn bò của mình. Sau khi phỏng vấn, anh ta chấm điểm cho những con bò ứng viên theo thang điểm gọi là "cowmpetency", hay còn gọi là "độ bảnh bò" cho mỗi con bò. Số điểm này dao động từ \(1\) đến \(C\) (\(1 \leq C \leq 10^9\)), với \(C\) là độ bảnh mà John mong muốn con bò đầu đàn của mình có được.
Do đã mệt mỏi sau khi phải phỏng vấn \(N\) con bò được đánh số từ \(1\) đến \(N\) (\(2 \leq N \leq 10^9\)), anh John đã quên mất độ bảnh của những con bò ứng viên. Tuy nhiên, anh vẫn nhớ được \(Q\) (\(1 \leq Q \leq \text{ min(N - 1,100)}\)) cặp số (\(a_1, a_h\)), trong đó bò \(h_1\) là con bò bảnh nhất trong dãy từ bò 1 đến bò \(a_i\) (vậy \(1 \leq a_i < h_i \leq N\)).
Anh John cho bạn biết bảng điểm của những con bò dưới dạng một dãy \(c_1, \ldots, c_N\) (với \(c_i\) = 0 nghĩa là anh John đã quên mất độ bảnh bò của con bò có số thứ tự \(i\)). Nhiệm vụ của bạn là giúp anh John nhớ lại bảng điểm nhỏ nhất theo thứ tự từ điển bằng những thông tin đã có. Biết một dãy điểm sẽ nhỏ hơn một dãy khác nếu tại điểm khác biệt nhỏ nhất có của dãy này nhỏ hơn.
Anh John đã phỏng vấn tất cả \(T\) (\(1 \leq T \leq 20\)) ngày và cần bạn giúp đỡ ngay lạp tức. Dữ liệu đảm bảo tổng số bò của cả \(T\) ngày không quá \(3 \times 10^5\).
Input
- Dòng đầu tiên chứa \(T\) là số câu hỏi anh John đặt ra cho bạn.
- Mỗi câu hỏi bao gồm:
- Dòng đầu tiên gồm \(N\), \(Q\) và \(C\).
- Dòng tiếp theo gồm \(c_1, \ldots, c_N\) là bảng điểm của những con bò
- Cuối cùng là \(Q\) dòng, mỗi dòng chứa một cặp (\(a_j, h_j\)). Dữ liệu đảm bảo mỗi \(a_j\) đều độc lập.
Output
- Gồm \(T\) dòng, mỗi dòng chứa kết quả của một bài toán, hoặc -1 nếu không có kết quả nào phù hợp.
Scoring
- Subtask \(1\): \(N \leq 10\) và \(Q,C \leq 4\)
- Subtask \(2\): \(N \leq 1000\)
- Subtask \(3\): Không có ràng buộc gì thêm.
Test 1
Input
1
7 3 5
1 0 2 3 0 4 0
1 2
3 4
4 5Output
1 2 2 3 4 4 1Note
Chúng ta có thể thấy rằng kết quả thỏa mãn tất cả các cặp mà nông dân John nhớ.
- max(\(c_1\)) = 1, \(c_2=2\) và \(1<2\) nên cặp đầu tiên được thỏa mãn.
- max(\(c_1,c_2,c_3\)) = 2, \(c_4 = 3\) và \(2<3\) nên cặp thứ hai được thỏa mãn.
- max(\(c_1,c_2,c_3,c_4\)) = 3, \(c5 = 4\) và \(3<4\) nên cặp thứ ba được thỏa mãn.
Có nhiều dãy số khác phù hợp với trí nhớ của Farmer John, chẳng hạn như:
1 2 2 3 5 4 1
1 2 2 3 4 4 5
Tuy nhiên, kết quả đưa ra là nhỏ nhất theo thứ tự từ điển.
Test 2
Input
5
7 6 10
0 0 0 0 0 0 0
1 2
2 3
3 4
4 5
5 6
6 7
8 4 9
0 0 0 0 1 6 0 6
1 3
6 7
4 7
2 3
2 1 1
0 0
1 2
10 4 10
1 2 0 2 1 5 8 6 0 3
4 7
1 2
5 7
3 7
10 2 8
1 0 0 0 0 5 7 0 0 0
4 6
6 9Output
1 2 3 4 5 6 7
1 1 2 6 1 6 7 6
-1
1 2 5 2 1 5 8 6 1 3
-1Note
Trong test case số 3, vì \(C=1\), dãy số duy nhất có thể là 1 1. Tuy nhiên, trong trường hợp này, bò 2 không có điểm số lớn hơn bò 1, vì vậy chúng ta không thể thỏa mãn điều kiện.
Trong test case số 5, \(a_1\) và \(h_1\) cho chúng ta biết rằng bò 6 là bò đầu tiên có điểm số lớn hơn các bò từ 1 đến 4. Do đó, điểm số lớn nhất cho các bò từ 1 đến 6 là của bò 6: 5. Vì bò 7 có điểm số 7, bò 7 là bò đầu tiên có điểm số lớn hơn các bò từ 1 đến 6. Do đó, phát biểu thứ hai rằng bò 9 là bò đầu tiên có điểm số lớn hơn các bò từ 1 đến 6 không thể đúng.
Bình luận (1)