레이팅 미적용농부 존은 줄 \(a\)에 소 \(N\)마리(\(1 \leq N \leq 2 \cdot 10^5\))를 세워 두었다. 줄 \(a\)의 앞에서 \(i\)번째 소에는 정수 \(a_i\)(\(1 \leq a_i \leq N\))가 붙어 있다. 여러 소가 같은 정수를 가질 수 있다.
농부 존은 다음과 같은 방법으로 또 다른 줄 \(b\)를 만든다.
- 처음에 \(b\)는 비어 있다.
- \(a\)가 비어 있지 않은 동안, \(a\)의 맨 앞에 있는 소를 제거하고, 그 소를 \(b\)의 맨 뒤에 추가할지 말지 선택한다.
농부 존은 \(b\)의 앞에서 뒤로 읽은 라벨 수열이 사전순으로 가장 크도록 줄 \(b\)를 만들고 싶다(각주 참고).
농부 존은 줄 \(b\)를 만들기 전에 다음 연산을 최대 한 번 수행할 수 있다.
- 줄 \(a\)에서 소 한 마리를 골라 현재 위치보다 앞의 아무 곳으로나 옮긴다.
농부 존이 위 연산을 최대 한 번 최적으로 수행했을 때, 그가 얻을 수 있는 사전순으로 가장 큰 \(b\)의 라벨 수열을 출력하시오.
각 입력은 \(T\)개(\(1 \leq T \leq 100\))의 독립적인 테스트 케이스로 이루어진다.
Problem credits: Chongtian Ma, Haokai Ma, Andrew Li
배점
- 입력 2-4: \(N \leq 100\)
- 입력 5-8: \(N \leq 750\)
- 입력 9-18: 추가 제약이 없다
각주
수열 \(s\)가 수열 \(t\)보다 사전순으로 크다는 것은 다음 중 하나가 성립하는 것과 동치임을 상기하라.
- \(s_i \neq t_i\)인 첫 번째 위치 \(i\)에서 \(s_i > t_i\)이다.
- 그러한 \(i\)가 존재하지 않으면, \(s\)가 \(t\)보다 길다.
Problem credits: Chongtian Ma, Haokai Ma, Andrew Li
첫째 줄에 \(T\)가 주어진다.
각 테스트 케이스의 첫째 줄에 \(N\)이 주어진다.
각 테스트 케이스의 둘째 줄에 공백으로 구분된 정수 \(N\)개 \(a_1, a_2, \ldots, a_N\)이 주어진다.
모든 테스트 케이스에 대한 \(N\)의 합은 \(10^6\)을 넘지 않음이 보장된다.
각 테스트 케이스마다 사전순으로 가장 큰 \(b\)를 새로운 줄에 출력한다.
3
5
4 3 2 1 3
6
5 1 2 6 3 4
6
4 1 3 2 1 14 3 3 2 1
6 5 4
4 3 2 1 1In the first test case, FJ can move the fifth cow to directly after the second
cow. Now, \(a = [4, 3, 3, 2, 1]\). It can be shown \([4, 3, 3, 2, 1]\) is also the
lexicographically greatest \(b\).
In the second test case, FJ can move the fourth cow to the front of the line.
In the third test case, FJ does not need to perform any operations. He can
construct \(b\) by adding each cow beside the second cow to the back of \(b\). It
can be shown this results in the lexicographically greatest \(b\).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > February > Silver