Bessie's Interview
플래티넘 V의견: 0
Bessie is looking for a new job! Fortunately, \(K\) farmers are currently hiring
and conducting interviews. Since jobs are highly competitive, the farmers have
decided to number and interview cows in the order they applied. There are \(N\)
cows that applied before Bessie, so her number is \(N+1\)
(\(1 \leq K \leq N \leq 3 \cdot 10^5\)).
The interview process will go as follows. At time \(0\), farmer \(i\) will start
interviewing cow \(i\) for each \(1 \leq i \leq K\). Once a farmer finishes an
interview, he will immediately begin interviewing the next cow in line. If
multiple farmers finish at the same time, the next cow may choose to be
interviewed by any of the available farmers, according to her preference.
For each \(1\le i\le N\), Bessie already knows that cow \(i\)'s interview will take
exactly \(t_i\) minutes (\(1 \leq t_i \leq 10^9\)). However, she doesn't know each
cow's preference of farmers.
Since this job is very important to Bessie, she wants to carefully prepare for
her interview. To do this, she needs to know when she will be interviewed and
which farmers could potentially interview her. Help her find this information!
Problem credits: Avnith Vijayram
SCORING
- Inputs 2-3: No two farmers finish at the same time.
- Inputs 4-9: \(N\le 3\cdot 10^3\)
- Inputs 10-21: No additional constraints.
Problem credits: Avnith Vijayram
The first line of the input will contain two integers \(N\) and \(K\).
The second line will contain \(N\) integers \(t_1 \dots t_N\).
On the first line, print the time Bessie's interview will begin.
On the second line, a bit string of length \(K\), where the \(i\)-th bit is \(1\) if
farmer \(i\) could interview Bessie and \(0\) otherwise.
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
평가 및 의견
Bessie's Interview
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Bessie's Interview