루미 알고리즘

#1645플래티넘Lieutenant's Lotto

PO 2026 훈련 캠프코딩출제 Nils Gustafsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Lieutenant's Lotto is a game whose rules are as follows: You are given a positive integer N and a list of numbers p_1, p_2, …, p_N such that every integer from 1 to N is present in the list (i.e. it is a permutation). The objective is to find an N × N grid of zeroes and ones, such that

  1. No two rows are identical, and
  2. The ith row is equal to the p_ith column, for every 1 ≤ i ≤ N.

Your task is to construct such a grid, if possible.

Input

The first line contains one integer N (2 ≤ N ≤ 1000).

The second line contains N integers p_1, p_2, …, p_N (1 ≤ p_i ≤ N). Every integer from 1 to N is present in this list of numbers.

Output

If a valid grid exists, print one line with “YES”, followed by N lines, each containing a string of length N. These N lines constitute the grid.

If a valid grid does not exist, print “NO”.

Scoring

Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.

GroupPointsConstraints
111p_i = i for all 1 ≤ i ≤ N.
212N ≤ 5
315p_i = i+1 for every 1 ≤ i ≤ N-1, and p_N = 1.
424p_{p_i} ≠ i for all 1 ≤ i ≤ N.
538No additional constraints.

Explanation of Samples

In the first sample, the first row and the second column are both 1100, which means that they are equal. The other rows also correspond to their respective columns.

In the second sample, the only way to make the rows equal to their corresponding column is by having the grid be all zeros or all ones. But then the rows would not be different.

예제

예제 1

입력
4
2 3 1 4
출력
YES
1100
0110
1010
0001

예제 2

입력
2
2 1
출력
NO

출처 표기

출처: Programmeringsolympiaden 2026년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.