15369. Karte (Gold I)
$n$장의 카드가 주어진다. 각 카드에는 어떤 정수 $a_i$에 대해 “이 카드의 밑에 있는 카드들 중 적어도 $a_i$장의 카드에 쓰여 있는 문장은 거짓이다"라는 문장이 적혀 있다.
이 카드들을 적절한 순서로 쌓아 정확히 $k$장의 카드가 거짓이 되도록 하시오.
- 입력 제한: $1 \le n \le 5 \times 10^5$, $0 \le k \le n$, $0 \le a_i \le 5 \times 10^5$
관찰
$k$장이 거짓일 때 각 카드가 가질 수 있는 값의 범위를 알아보자.
- $k = 0$인 경우:
0 0 0 0 ... 0 - $k = 1$인 경우:
0-1 0-1 ... 0-1 1-inf 0 0 ... 0 - $k = 2$인 경우:
0-2 0-2 ... 0-2 2-inf 0-1 0-1 ... 0-1 1-inf 0 0 ... 0
0이 적혀 있는 카드는 항상 참이다. 또한, $k$를 초과하는 값이 적혀 있는 카드는 항상 거짓이다. 항상 거짓인 카드들은 모두 $k$개의 거짓 자리 중 하나에 놓아야 한다. 따라서 이러한 카드가 $k$장을 초과하면 답은 불가능이다.
항상 거짓인 카드가 $f$장이라면, $k-f$개의 자리를 1에서 $k$ 사이의 카드로 채워야 한다. 이러한 카드가 부족하다면 역시 답은 불가능이다.
거짓 자리는 오른쪽으로 갈수록 가능한 수의 범위가 넓어지므로, 항상 거짓인 카드는 왼쪽부터 채우는 것이 항상 이득이다.
남은 거짓 자리 또한 남은 카드 중에서 가장 큰 값부터 골라서 왼쪽부터 채우는 것이 이득이다. 그렇게 채우다가 어느 시점에 범위를 만족할 수 없게 되면 답은 불가능이다.
거짓 자리를 모두 채웠다면 남은 카드는 각 구간의 범위에 맞게 놓으면 되는데, 사실 그냥 맨 앞 구간이 범위가 가장 넓기 때문에 맨 앞에 몰아넣어도 된다. 코드를 짤 때에는 이 생각을 못 해서 $k$를 모두 넣고 거짓 한 장 넣고, $k-1$을 모두 넣고 거짓 한 장 넣고, …의 구성을 했다. 아무튼 범위 조건을 만족하기만 하면 된다.