레이팅 미적용베시는 새 일자리를 찾고 있다! 다행히 현재 \(K\)명의 농부가 채용을 진행하며 면접을 보고 있다. 일자리 경쟁이 매우 치열하기 때문에, 농부들은 소들에게 지원한 순서대로 번호를 매기고 그 순서대로 면접을 보기로 했다. 베시보다 먼저 지원한 소가 \(N\)마리 있으므로 베시의 번호는 \(N+1\)이다 (\(1 \leq K \leq N \leq 3 \cdot 10^5\)).
면접은 다음과 같이 진행된다. 시각 \(0\)에, 각 \(1 \leq i \leq K\)에 대해 농부 \(i\)는 소 \(i\)의 면접을 시작한다. 어떤 농부가 면접을 마치면, 곧바로 줄에서 다음 차례인 소의 면접을 시작한다. 여러 농부가 동시에 면접을 마치면, 다음 소는 자신의 선호에 따라 면접 가능한 농부들 중 아무나 선택할 수 있다.
각 \(1\le i\le N\)에 대해, 베시는 소 \(i\)의 면접이 정확히 \(t_i\)분 걸린다는 것을 이미 알고 있다 (\(1 \leq t_i \leq 10^9\)). 하지만 각 소가 어떤 농부를 선호하는지는 알지 못한다.
이 일자리는 베시에게 매우 중요하므로, 베시는 면접을 꼼꼼히 준비하고 싶다. 그러려면 자신이 언제 면접을 보게 되는지, 그리고 어떤 농부들이 자신을 면접할 가능성이 있는지 알아야 한다. 이 정보를 찾도록 도와주자!
문제 제공: Avnith Vijayram
배점
- 입력 2-3: 어떤 두 농부도 동시에 면접을 마치지 않는다.
- 입력 4-9: \(N\le 3\cdot 10^3\)
- 입력 10-21: 추가 제약 없음.
문제 제공: Avnith Vijayram
첫째 줄에 두 정수 \(N\)과 \(K\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(t_1 \dots t_N\)이 주어진다.
첫째 줄에 베시의 면접이 시작되는 시각을 출력한다.
둘째 줄에 길이 \(K\)의 비트 문자열을 출력한다. \(i\)번째 비트는 농부 \(i\)가 베시를 면접할 가능성이 있으면 \(1\), 그렇지 않으면 \(0\)이다.
6 3
3 1 4159 2 6 58
110There are \(6\) cows aside from Bessie and \(3\) farmers, and the interview process will go as
follows:
- At time \(t = 0\), farmer \(1\) interviews cow \(1\), farmer \(2\) interviews cow \(2\), and farmer \(3\) interviews cow \(3\).
- At time \(t = 1\), farmer \(2\) finishes his interview with cow \(2\) and starts interviewing cow \(4\).
- At time \(t = 3\), both farmer \(1\) and farmer \(2\) finish their interviews, and there are two possibilities: - Farmer \(1\) interviews cow \(5\) and farmer \(2\) interviews cow \(6\). In this case, farmer \(2\) would finish his interview at time \(t = 8\) and start interviewing Bessie. - Farmer \(1\) interviews cow \(6\) and farmer \(2\) interviews cow \(5\). In this case, farmer \(1\) would finish his interview at time \(t = 8\) and start interviewing Bessie.
Thus, Bessie's interview will begin at time \(t = 8\), and she could be
interviewed by either farmer \(1\) or farmer \(2\).
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > US Open > Silver