Trao Huy Chương BeRC

Điểm: 4,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Một kỳ thi lập trình vừa kết thúc với $n$ thí sinh tham gia. Bảng xếp hạng đã được sắp xếp giảm dần theo số bài giải được: thí sinh đứng thứ $i$ giải được $p_{i}$ bài, và $p_{1} \geq p_{2} \geq \dots \geq p_{n}$ .

Ban giám khảo cần phân phối huy chương vàng, bạc, đồng. Gọi số huy chương mỗi loại lần lượt là $g$ , $s$ , $b$ . Quy chế trao giải gồm các điều kiện sau, tất cả phải đồng thời được thoả mãn:

Mỗi loại huy chương phải được trao ít nhất một chiếc: $g > 0$ , $s > 0$ , $b > 0$ .
Số huy chương vàng phải nhỏ hơn nghiêm ngặt số huy chương bạc và số huy chương đồng: $g < s$ và $g < b$ (không có ràng buộc giữa $s$ và $b$ ).
Mỗi thí sinh được vàng phải giải được nhiều hơn nghiêm ngặt so với mọi thí sinh được bạc.
Mỗi thí sinh được bạc phải giải được nhiều hơn nghiêm ngặt so với mọi thí sinh được đồng.
Mỗi thí sinh được đồng phải giải được nhiều hơn nghiêm ngặt so với mọi thí sinh không được huy chương.
Tổng số người được huy chương $g + s + b$ không vượt quá một nửa tổng số thí sinh, tức $g + s + b \leq ⌊ n / 2 ⌋$ .

Ban giám khảo muốn trao huy chương cho càng nhiều thí sinh càng tốt (tức tối đa hoá $g + s + b$ ) sao cho tất cả các điều kiện trên đều được thoả mãn. Hãy giúp tìm một cách trao huy chương như vậy.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ ( $1 \leq t \leq 10000$ ) — số test trong dữ liệu vào. Sau đó là $t$ test.

Mỗi test gồm hai dòng:

Dòng thứ nhất chứa số nguyên $n$ ( $1 \leq n \leq 4 \cdot 10^{5}$ ) — số thí sinh.
Dòng thứ hai chứa $n$ số nguyên $p_{1}, p_{2}, \dots, p_{n}$ ( $0 \leq p_{i} \leq 10^{6}$ ), đã sắp xếp giảm dần: $p_{1} \geq p_{2} \geq \dots \geq p_{n}$ .

Dữ liệu ra

In ra $t$ dòng, dòng thứ $j$ là kết quả của test thứ $j$ .

Mỗi kết quả gồm ba số nguyên không âm $g$ , $s$ , $b$ :

In ra $g = s = b = 0$ nếu không tồn tại cách trao huy chương thoả mãn mọi điều kiện.
Ngược lại, in ra ba số dương $g$ , $s$ , $b$ — số huy chương vàng, bạc, đồng có thể trao, với $g + s + b$ lớn nhất có thể. Nếu có nhiều đáp án cùng tối ưu, in ra một đáp án bất kỳ.

Ràng buộc

$1 \leq t \leq 10000$
$1 \leq n \leq 4 \cdot 10^{5}$
$0 \leq p_{i} \leq 10^{6}$
$p_{1} \geq p_{2} \geq \dots \geq p_{n}$
Tổng các $n$ trên mọi test không vượt quá $4 \cdot 10^{5}$ .

Ví dụ

Input	Output	Giải thích
5 12 5 4 4 3 2 2 1 1 1 1 1 1 4 4 3 2 1 1 1000000 20 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 32 64 64 63 58 58 58 58 58 37 37 37 37 34 34 28 28 28 28 28 28 24 24 19 17 17 17 17 16 16 16 16 11	1 2 3 0 0 0 0 0 0 1 2 7 2 6 6	Test 1: trao $1$ vàng (người giải $5$ bài), $2$ bạc (hai người giải $4$ bài), $3$ đồng (ba người giải $2$ hoặc $3$ bài). Tổng $6 \leq 12 / 2$ . Mọi $(g, s, b)$ khác đạt cùng tổng cực đại đều được chấp nhận. Test 2, 3: không thể vì $g + s + b$ phải $\geq 3$ nhưng không vượt quá $⌊ n / 2 ⌋$ . Test 4: tổng tối đa là $10$ ; các đáp án $2 5 3$ hoặc $1 3 6$ cũng hợp lệ. Test 5: tổng tối đa là $14$ .
1 12 7 5 5 5 3 2 1 1 1 1 1 1	1 3 2	Vàng = ${7}$ ( $g = 1$ ); bạc = ba thí sinh giải $5$ bài ( $s = 3$ ); đồng = hai thí sinh giải $3$ và $2$ bài ( $b = 2$ ). Tổng $6 = 12 / 2$ đạt cực đại. Các điều kiện $g < s$ , $g < b$ , và các tầng điểm phân tách nghiêm ngặt đều thoả.

Bình luận

Không có bình luận tại thời điểm này.