22881번 - 붉은색 푸른색 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 32 MB (추가 메모리 없음) | 103 | 34 | 17 | 33.333% |
문제
메모리 제한에 유의하세요.
어린 시절 제연이는 $1$부터 $N$까지의 번호가 쓰여 있는 $N$개의 구슬을 가지고 있었다. 각 구슬은 붉은색 또는 푸른색을 띠고 있었으며, 제연이는 구슬들을 $N$개의 서로 다른 주머니에 하나씩 넣어 보관했다.
제연이는 구슬들을 소중히 여겼다. 그래서 매일매일 구슬들을 가지고 한 행동들을 모두 일기장에 순서대로 기록했다. 제연이가 일기장에 기록한 일은 다음 세 종류 중 하나이다.
1 i j: $i$번 구슬이 들어 있는 주머니와 $j$번 구슬이 들어 있는 주머니를 합친다. ($1\leq i, j \leq N$)2 i: $i$번 구슬을 갖고 놀다가 잃어버린다. ($1\leq i \leq N$) 슬프게도 잃어버린 구슬은 영영 다시 찾지 못했다.3 i l h: $i$번 구슬이 들어 있는 주머니를 관찰한다. 그 주머니에는 붉은색 구슬이 $l$개 이상 $h$개 이하 들어 있었다. ($1 \leq i \leq N, 0 \leq l \leq h \leq N$)
10년이 지난 뒤, 제연이는 $M$개의 기록이 적혀 있는 일기장을 발견했다. 그 시절의 순수함을 잃어버린 제연이는 일기장을 보고 각 구슬의 색깔을 복원하기로 했다. 혼자서 색깔을 복원할 생각을 하니 눈앞이 샛노래진 제연이를 도와주자.
단, 구슬은 항상 주머니에 넣어서 보관했으며, 일기장에 기록되지 않은 구슬의 이동이나 변화는 없었다고 가정한다.
입력
첫째 줄에 정수 $N$과 $M$($2 \leq N \leq 2\ 000,\, 1 \leq M \leq 4\ 000$)이 주어진다.
둘째 줄부터 $M$개의 줄에 일기장의 기록이 위에서 설명한 형식으로 주어진다. 이전에 잃어버리지 않은 구슬만 기록에 등장하며, 1번 종류의 기록에서 $i$번 구슬과 $j$번 구슬은 다른 주머니에 속해 있는 상태였음이 보장된다.
출력
$M$개의 기록을 모두 만족하는 $N$개 구슬의 색깔 조합이 존재한다면 YES를, 존재하지 않는다면 NO를 출력한다.
그러한 색깔 조합이 존재한다면, 다음 줄에 길이 $N$의 문자열을 출력한다. 문자열의 $i$번째 문자는 $i$번 구슬이 붉은색이면 R, 푸른색이면 B이다. 답이 여러 가지라면 아무것이나 출력해도 된다.
예제 입력 1
5 9 1 2 4 1 1 5 3 4 1 2 3 5 0 1 1 4 1 3 4 2 5 2 1 3 4 0 1 3 3 1 1
예제 출력 1
YES RBRRB
예제 입력 2
3 4 1 1 2 3 2 1 2 1 2 3 3 3 0 0
예제 출력 2
NO
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호