Đấu Trường Bitmask Tối Thượng

Buổi 23 — Thao tác bit
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Có $N$ chiến binh tham gia giải đấu. Giải đấu diễn ra theo từng vòng: mỗi vòng, bạn chọn đúng $2$ chiến binh còn lại để đấu, người thua bị loại. Kết quả đối đầu trực tiếp giữa mọi cặp chiến binh được cho trước dưới dạng ma trận thắng/thua.

Bạn được quyền sắp xếp thứ tự các trận đấu. Với mỗi chiến binh $i$, hãy xác định xem liệu tồn tại một cách sắp xếp các trận đấu sao cho chiến binh $i$ là người chiến thắng cuối cùng hay không.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$.
  • Tiếp theo là $N$ dòng, mỗi dòng chứa $N$ ký tự (Y hoặc N). Ký tự thứ $j$ trên dòng thứ $i$ là Y nếu chiến binh $i$ thắng chiến binh $j$ khi đấu trực tiếp, N nếu ngược lại. Đảm bảo rằng ma trận kết quả nhất quán (nếu $i$ thắng $j$ thì $j$ thua $i$ với $i \ne j$) và ô chéo chính là N.
Dữ liệu ra
  • In ra một dòng gồm $N$ ký tự. Ký tự thứ $i$ là 1 nếu chiến binh $i$ có thể là người chiến thắng, ngược lại là 0.
Ví dụ
Input Output
3
NYY
NNY
NNN
100
Giới hạn
  • $2 \le N \le 14$
Draft saved