trang chủ / đề bài / icpc24_nat_h

Trung vị cố định

Đề bài

Mô tả

Với một dãy a gồm n số nguyên không âm a0,a1,…,an−1, trong đó n lẻ, trung vị của a là phần tử thứ n−12 (đánh số từ 0) khi sắp xếp các phần tử theo thứ tự tăng dần. Ví dụ:

  • Với a=[5,7,8], trung vị là 7 (dãy đã được sắp xếp, và an−12=a1=7).
  • Với a=[4,8,6,0,2], trung vị là 4 (sau khi sắp xếp ta được [0,2,4,6,8], và an−12=a2=4).
  • Với a=[0,100,0], trung vị là 0.

Cho dãy b gồm n số nguyên không âm b0,b1,…,bn−1 với n lẻ, và một số nguyên không âm x. Một số phần tử của b bị mất (được ký hiệu là bi=−1). Hãy khôi phục các phần tử bị mất sao cho trung vị của b đúng bằng x, hoặc cho biết điều đó là không thể.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương t (1≤t≤104): số bộ test. Mỗi bộ test gồm:

  • Dòng thứ nhất chứa hai số nguyên n và x (1≤n<2·105, n lẻ, 0≤x≤109): độ dài dãy b và giá trị trung vị cần đạt.
  • Dòng thứ hai chứa n số nguyên b0,b1,…,bn−1 (−1≤bi≤109): các phần tử của b, trong đó bi=−1 nghĩa là bi bị mất.

Dữ liệu đảm bảo tổng n trên tất cả các bộ test không vượt quá 2·105.

Dữ liệu ra

Với mỗi bộ test, in ra "YES" (không có dấu ngoặc kép) nếu có cách khôi phục các phần tử bị mất để trung vị của b bằng x. Ngược lại, in ra "NO".

Nếu đáp án là "YES", dòng tiếp theo in ra n số nguyên b0′,b1′,…,bn−1′ (0≤bi′≤109) là dãy b sau khi khôi phục (các phần tử đã biết giữ nguyên). Nếu có nhiều dãy b′ thỏa mãn, in ra một dãy bất kỳ. Có thể chứng minh rằng với ràng buộc của bài, nếu tồn tại dãy b′ hợp lệ thì cũng tồn tại một dãy b′ có mọi phần tử nằm trong đoạn [0,109].

Ràng buộc

  • 1≤t≤104
  • 1≤n<2·105, n lẻ; tổng n trên tất cả các bộ test không vượt quá 2·105
  • 0≤x≤109, −1≤bi≤109

Ví dụ

Input Output Giải thích
5
3 2
0 -1 2
5 4
4 -1 6 0 -1
7 8
2 5 6 8 9 10 11
7 9
2 5 6 8 9 10 11
5 8
4 4 4 -1 -1
YES
0 2 2
YES
4 4 6 0 4
YES
2 5 6 8 9 10 11
NO
NO
Bộ test thứ nhất: b′=[0,2,2] có trung vị 2; b′=[0,4,2] cũng hợp lệ. Bộ test thứ hai: b′=[4,4,6,0,4] có trung vị 4; [4,8,6,0,2] cũng hợp lệ. Bộ test thứ ba: cách khôi phục duy nhất là giữ nguyên b, trung vị là 8. Bộ test thứ tư: trung vị của b là 8, khác x=9. Bộ test thứ năm: trung vị luôn là 4 dù khôi phục thế nào.
3
1 5
-1
1 0
7
3 0
-1 -1 1
YES
5
NO
YES
0 0 1
Bộ test thứ hai: không có phần tử bị mất, trung vị là 7≠0. Bộ test thứ ba: [0,0,1] có trung vị 0.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0