trang chủ / bài tập / fencepnt

Sơn hàng rào

Đề bài

Mô tả

Một hàng rào gồm n tấm ván xếp theo thứ tự từ 1 đến n. Tấm ván thứ i đang có màu ai, và bạn muốn nó có màu bi.

Bạn đã thuê m thợ sơn. Thợ thứ j đến vào thời điểm j (nghĩa là các thợ làm việc lần lượt theo thứ tự 1,2,,m) và sẽ sơn lại đúng một tấm ván bằng màu cj. Với mỗi thợ bạn được chọn tấm ván mà thợ đó sơn, nhưng không được từ chối thợ nào: mỗi thợ bắt buộc phải sơn đúng một tấm ván. Nhiều thợ có thể cùng sơn một tấm ván, khi đó màu cuối cùng của tấm ván là màu của thợ đến sau cùng trong số đó.

Hãy xác định xem có thể thu được hàng rào với màu mong muốn b hay không. Nếu có, hãy chỉ ra tấm ván mà mỗi thợ phải sơn.

Dữ liệu vào

  • Dòng đầu tiên chứa một số nguyên t là số bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm bốn dòng:
    • Dòng thứ nhất chứa hai số nguyên nm: số tấm ván và số thợ sơn.
    • Dòng thứ hai chứa n số nguyên a1,a2,,an: màu ban đầu của các tấm ván.
    • Dòng thứ ba chứa n số nguyên b1,b2,,bn: màu mong muốn của các tấm ván.
    • Dòng thứ tư chứa m số nguyên c1,c2,,cm: màu sơn mà các thợ mang theo.

Dữ liệu ra

Với mỗi bộ dữ liệu:

  • In ra NO nếu không thể thu được cách tô màu b.
  • Ngược lại, in ra YES trên một dòng, rồi in ra m số nguyên x1,x2,,xm trên dòng tiếp theo, trong đó xj là chỉ số tấm ván mà thợ thứ j phải sơn.

Nếu có nhiều đáp án, in ra một đáp án bất kỳ. Chữ hoa hay chữ thường của YES / NO đều được chấp nhận.

Ràng buộc

  • 1t104
  • 1n,m105
  • 1ai,bin
  • 1cjn
  • Tổng n trên tất cả các bộ dữ liệu không vượt quá 105, và tổng m cũng không vượt quá 105.

Ví dụ

Input Output Giải thích
3
1 1
1
1
1
3 4
1 1 1
2 1 1
3 3 3 2
3 4
1 1 1
2 1 1
2 3 3 3
YES
1
YES
1 1 1 1
NO
Bộ 1: tấm ván duy nhất đã đúng màu, thợ duy nhất sơn lại nó bằng chính màu đó nên không làm hỏng gì.
Bộ 2: ba thợ đầu mang màu 3 vô dụng, nhưng họ cùng sơn lên tấm ván 1 vì thợ cuối sẽ phủ màu 2 lên đó.
Bộ 3: cùng tập màu nhưng thợ cuối mang màu 3, mà 3 không có trong b; tấm ván anh ta sơn sẽ giữ màu 3 đến cuối nên chắc chắn sai.
2
10 5
7 3 2 1 7 9 4 2 7 9
9 9 2 1 4 9 4 2 3 9
9 9 7 4 3
6 4
3 4 2 4 1 2
2 3 1 3 1 1
2 2 3 4
YES
1 2 5 5 9
NO
Bộ 1: bốn tấm ván 1,2,5,9 đang sai màu và được đúng bốn thợ 1,2,4,5 sửa; thợ 3 mang màu 7 không cần đến nên sơn tạm lên tấm ván 5, sau đó thợ 4 phủ màu 4 lên. Nhiều đáp án khác cũng hợp lệ.
Bộ 2: không đủ thợ mang màu cần thiết nên không thể đạt được b.

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.400 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.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0