3430번 - 용이 산다 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 128 MB | 1268 | 319 | 202 | 27.446% |
문제
옛날 아주 먼 옛날, 한 마을에 용이 살고 있었습니다. 그 마을에는 호수가 여러개 있었는데, 그 호수들은 모두 물이 들어 있었습니다. 이 마을에는 가끔 비가 내립니다. 신기하게도 비는 한 호수 위에서만 내린다고 합니다. 비가 내렸을 때 그 호수가 비어있다면 그 호수는 다시 물로 꽉 차지만, 만약 호수에 물이 있는데 다시 비가 내릴경우 호수가 넘쳐 흘러서 엄청난 재앙을 불러 일으킬 수 있었습니다. 용은 비가 오지 않는 날에는 하루에 한개의 호수에 있는 물을 전부 먹어 치울 수 있었지만, 비가 오는 날에는 물을 마시지 못했습니다. 용은 신비한 능력을 가지고 있어서 언제 어디서 비가 올지를 정확히 알아낼 수 있었기 때문에, 비가 오기 전 그 호수의 물을 전부 먹어치울 수 있었고 마을사람들은 행복하게 살았답니다.
그런데 어느 여름날, 장맛비가 찾아왔습니다. 용은 언제 어디서 호수의 물을 먹을지를 계산하려고 했지만, 엄청난 양의 비에 당황한 나머지 실패하고 말았답니다. 여러분이 용을 도와서 재앙으로부터 마을을 지켜주세요!
입력
첫 번째 줄에는 테스트 케이스의 수 Z가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 두 개의 자연수 n,m이 주어진다. n은 호수의 개수이고, m은 호수에 비가 내리는 날의 수이다. (n ≤ 106, m ≤ 106)
각 테스트 케이스의 두 번째 줄에는 m개의 정수 t1, t2, t3,...,tm 이 주어진다. (0 ≤ ti ≤ n) 만약 ti가 자연수라면 i번째 날에는 ti번 호수에서 비가 내림을 의미한다. ti가 0이라면 i번째 날에는 비가 오지 않음을 의미하고, 이 날은 용이 호수로부터 물을 마실 수 있다. 용은 비가 오는 날에는 물을 마시지 않는다는 사실을 기억하라.
출력
첫 번째 줄에 만약 재앙을 막을 수 있다면 YES를, 막을 수 없다면 NO를 출력한다.
만약 YES인 경우에는 두 번째 줄에 ℓ개의 자연수 또는 0을 출력한다. (이때 ℓ은 일기예보에서 주어진 0의 개수, 즉 비가 오지 않는 날의 수이다.) 각 자연수는 용이 물을 마셔야 할 호수의 번호를 나타내며, 만약 0일 경우는 아무 호수에서도 물을 마시지 않음을 의미한다. (아무리 용이라도 빈 호수에서는 물을 마실 수 없기 때문이다.)
예제 입력 1
4 2 4 0 0 1 1 2 4 0 1 0 2 2 3 0 1 2 2 4 0 0 0 1
예제 출력 1
NO YES 1 2 NO YES 0 1 0
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호