35491번 - [R] RPS Tournament 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 10 | 6 | 6 | 85.714% |
문제
히비는 올해 열리는 가위바위보 토너먼트를 운영하게 되었다. 이 토너먼트에는 패를 $N$개 사용하는 확장된 가위바위보를 사용하여 우승자를 결정한다.
패를 $N$개 사용하는 확장된 가위바위보의 규칙은 다음과 같다.
- 각 패에는 $1$번부터 $N$번까지의 고유한 번호가 붙어있다.
- $1 \le i \le N$과 $1\le k\le\left\lfloor \frac{N}{2} \right\rfloor$에 대해 $i$번 패는 $(i-k-1) \bmod N + 1$번 패를 이긴다.
- $1 \le i, j \le N$에 대해 $i$번 패가 $j$번 패를 이긴다면 $j$번 패는 $i$번 패한테 진다.
- $1 \le i \le N$에 대해 $i$번 패와 $i$번 패는 비긴다.
이번 토너먼트에서는 $N$명의 사람들이 참가하며, 각자 $1$부터 $N$까지의 고유한 번호가 붙어있다. 또한, 토너먼트의 원활한 진행을 위해 $i$번 참가자는 토너먼트가 진행되는 동안 항상 $i$번 패만 내야 한다.
이 대회는 토너먼트인 만큼 대진표가 있다. 대진표는 다음 조건을 만족하는 이진 트리이다.
- $N$개의 말단 정점이 있다. $i$번 말단 정점은 $L_i$번 참가자와 대응한다.
- 말단 정점이 아닌 모든 정점은 정확히 $2$개의 자식 정점을 가진다.
- 말단 정점이 아닌 어떠한 정점 $v$가 $c$개의 말단 정점을 자손으로 가진다고 하자. 이때, $v$의 왼쪽 자식은 정확히 $\left\lfloor \frac{c}{2} \right\rfloor$개의 말단 정점을 자손으로 가져야 한다.
- 왼쪽에 있는 말단 정점의 번호는 오른쪽에 있는 말단 정점의 번호보다 항상 작아야 한다.
예로, 아래는 $5$명이 참가하는 대진표이다. 정점에 적힌 번호는 말단 정점의 번호로, 참가자의 번호가 아님에 주의하자.
히비는 정수 $H$를 좋아하기 때문에, 참가자들의 배치 $L_1,L_2,\ldots ,L_N$을 적당히 바꿔서 $H$번 참가자가 우승하는 배치를 만들기로 했다. 히비를 도와 $H$번 참가자가 우승하는 배치를 만들어보자!
입력
첫째 줄에는 토너먼트의 참가자 수 $N$과 히비가 좋아하는 정수 $H$가 공백으로 구분되어 주어진다. $(3\le N\le 200\, 000;$ $1\le H\le N;$ $N$은 홀수$)$
출력
첫째 줄에는 $H$번 참가자가 우승하는 배치가 존재한다면 Yes를, 아니면 No를 출력한다.
만약 $H$번 참가자가 우승하는 배치가 존재한다면 둘째 줄에는 참가자의 배치를 나타내는 $N$개의 정수 $L_1, L_2, \ldots, L_N$을 공백으로 구분하여 출력한다.
예제 입력 1
5 3
예제 출력 1
Yes 4 1 3 5 2
다음과 같이 토너먼트가 진행된다.
출처
- 문제를 만든 사람: hibye1217
- 문제를 검수한 사람: mujigae, pyb1031, utilforever
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호