Chia Hai Tập

Đề bài

Mô tả

Cho n số nguyên phân biệt p1,p2,,pn. Hãy chia tất cả các số này vào hai tập AB sao cho đồng thời thoả mãn hai điều kiện sau:

  • Nếu số x thuộc tập A thì số ax cũng phải thuộc tập A.
  • Nếu số x thuộc tập B thì số bx cũng phải thuộc tập B.

Một tập có thể rỗng, nghĩa là hoàn toàn hợp lệ khi tất cả các số cùng nằm trong một tập.

Hãy tìm một cách chia thoả mãn, hoặc cho biết điều đó là không thể.

Dữ liệu vào

  • Dòng đầu chứa ba số nguyên n, a, b.
  • Dòng thứ hai chứa n số nguyên phân biệt p1,p2,,pn.

Dữ liệu ra

  • Nếu tồn tại cách chia, in ra YES ở dòng đầu. Dòng thứ hai in ra n số nguyên b1,b2,,bn (mỗi bi bằng 0 hoặc 1): nếu bi=0 thì pi thuộc tập A, ngược lại pi thuộc tập B.
  • Nếu không thể chia, in ra NO.

Nếu có nhiều cách chia hợp lệ, in ra một cách bất kỳ.

Ràng buộc

  • 1n105
  • 1a,b109
  • 1pi109, các pi đôi một phân biệt.

Ví dụ

Input Output Giải thích
4 5 9
2 3 4 5
YES
0 0 1 1
Tập A={2,3}: với 252=3A, với 353=2A. Tập B={4,5}: với 494=5B, với 595=4B.
3 3 4
1 2 4
NO Số 4 không thể vào A (vì 34=1 không có) cũng không thể vào B (vì 44=0 không có), nên không có cách chia nào.

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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0