Dãy Luân Phiên
Xem dạng PDFCho dãy số nguyên ~a~ gồm ~n~ phần tử. Bạn cần chia các phần tử của dãy thành hai dãy con ∗, sao cho mỗi phần tử thuộc đúng một trong hai dãy con và đều thỏa mãn tính luân phiên.
Một dãy thỏa mãn tính luân phiên nếu quan hệ giữa hai phần tử liên tiếp luôn đổi chiều, tức là có dạng:
~a_1 < a_2~, ~a_2 > a_3~, ~a_3 < a_4~, ~\ldots~
hoặc
~a_1 > a_2~, ~a_2 < a_3~, ~a_3 > a_4~, ~\ldots~
Hai phần tử liên tiếp bằng nhau không được xem là hợp lệ.
Dãy có không quá một phần tử luôn được xem là luân phiên.
∗ Một dãy con của dãy ~a~ là một dãy có thể thu được bằng cách xóa đi một số phần tử (hoặc không phần tử nào) của ~a~ mà không thay đổi thứ tự của các phần tử còn lại.
Input
Dòng đầu tiên chứa số nguyên ~t~ ~(1 \le t \le 10\,000)~ — số lượng test case. Mô tả của mỗi test case như sau:
Dòng đầu tiên chứa số nguyên ~n~.
Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(-10^9 \le a_i \le 10^9)~.
Tổng ~n~ trên tất cả test case không vượt quá ~2 \cdot 10^5~.
Output
Với mỗi test case:
Nếu không thể chia, in ra NO.
Nếu có thể chia, in ra YES ở dòng đầu tiên. Dòng tiếp theo in ra ~n~ số nguyên ~c_1, c_2, \dots, c_n~.
Trong đó:
~c_i = 1~ nếu phần tử ~a_i~ thuộc dãy con thứ nhất.
~c_i = 2~ nếu phần tử ~a_i~ thuộc dãy con thứ hai.
Mỗi ~c_i~ phải bằng ~1~ hoặc ~2~.
Nếu có nhiều đáp án, bạn có thể in ra bất kỳ đáp án nào.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~500~ | ~\sum n \le 20~ |
| 2 | ~1000~ | ~\sum n \le 2000~ |
| 3 | ~1000~ | ~\sum n \le 200000~ |
| Tổng | ~2500~ |
Với mỗi test case, điểm số được tính như sau:
| Điều kiện | Điểm |
|---|---|
| In sai kết quả YES/NO | ~0\%~ |
| In đúng kết quả YES/NO, nhưng cách chia không hợp lệ | ~75\%~ |
| In đúng kết quả YES/NO và cách chia hợp lệ | ~100\%~ |
Lưu ý rằng nếu đáp án là YES, bạn vẫn cần in ra đủ ~n~ số ~c_1, c_2, \dots, c_n~. Nếu dãy này không hợp lệ, bài làm sẽ được chấm theo mức điểm partial ở trên.
Điểm của một subtask được tính bằng điểm thấp nhất trong tất cả các test case thuộc subtask đó.
Điểm của bài làm là tổng điểm của các subtask.
Sample Input 1
3
5
1 3 2 4 5
4
3 3 3 -1
6
1 5 2 7 3 8
Sample Output 1
YES
1 1 1 2 2
NO
YES
1 1 1 1 1 1
Notes
Ở test case thứ nhất, ta chia được thành:
Dãy con thứ nhất: ~1, 3, 2~
Dãy con thứ hai: ~4, 5~
Ở test case thứ hai, có ba phần tử bằng ~3~. Vì hai phần tử liên tiếp bằng nhau không hợp lệ, mỗi dãy con chỉ có thể chứa nhiều nhất một phần tử bằng ~3~. Do chỉ có hai dãy con, không thể chia hợp lệ.
Ở test case thứ ba, toàn bộ dãy ~1, 5, 2, 7, 3, 8~ đã là một dãy luân phiên. Lưu ý dãy rỗng hoặc có một phần tử cũng được xem là dãy luân phiên.
Bình luận