#PU1422. USACO 2024 US Open Contest, Silver — Problem 1. Bessie's Interview

    ID: 1660 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:open24来源:usaco.orgscoring:equal_test_cases二分答案堆

USACO 2024 US Open Contest, Silver — Problem 1. Bessie's Interview

USACO 2024 US Open Contest, Silver — Problem 1. Bessie's Interview

题目描述

Bessie is looking for a new job! Fortunately, KK 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 NN cows that applied before Bessie, so her number is N+1N+1 (1≤K≤N≤3⋅1051 \leq K \leq N \leq 3 \cdot 10^5). The interview process will go as follows. At time 00, farmer ii will start interviewing cow ii for each 1≤i≤K1 \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≤i≤N1\le i\le N, Bessie already knows that cow ii's interview will take exactly tit_i minutes (1≤ti≤1091 \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!

输入格式

The first line of the input will contain two integers NN and KK. The second line will contain NN integers t1…tNt_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 KK, where the ii-th bit is 11 if farmer ii could interview Bessie and 00 otherwise.

数据范围

Inputs 2-3: No two farmers finish at the same time. Inputs 4-9: N≤3⋅103N\le 3\cdot 10^3 Inputs 10-21: No additional constraints. Problem credits: Avnith Vijayram

样例

样例 1

6 3
3 1 4159 2 6 5
8
110
There 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$.