The Best Lineup
플래티넘 IV의견: 0
Farmer John has \(N\) \((1 \leq N \leq 2 \cdot 10^5)\) cows in a line \(a\). The
\(i\)'th cow from the front of line \(a\) is labeled an integer \(a_i\)
(\(1 \leq a_i \leq N\)). Multiple cows may be labeled the same integer.
FJ will construct another line \(b\) in the following manner:
- Initially, \(b\) is empty.
- While \(a\) is nonempty, remove the cow at the front of \(a\) and potentially add that cow to the back of \(b\).
FJ wants to construct line \(b\) such that the sequence of labels in \(b\) from
front to back is lexicographically greatest (see the footnote).
Before FJ constructs line \(b\), he can perform the following operation at most
once:
- Choose a cow in line \(a\) and move it anywhere before its current position.
Given that FJ optimally performs the aforementioned operation at most once,
output the lexicographically greatest label sequence of \(b\) he can achieve.
Each input will consist of \(T\) (\(1 \leq T \leq 100\)) independent test cases.
Problem credits: Chongtian Ma, Haokai Ma, Andrew Li
SCORING
- Inputs 2-4: \(N \leq 100\)
- Inputs 5-8: \(N \leq 750\)
- Inputs 9-18: No additional constraints
FOOTNOTE
Recall that a sequence \(s\) is lexicographically greater than a sequence \(t\) if
and only if one of the following holds:
- At the first position \(i\) where \(s_i \neq t_i\), \(s_i > t_i\).
- If no such \(i\) exists, \(s\) is longer than \(t\).
Problem credits: Chongtian Ma, Haokai Ma, Andrew Li
The first line contains \(T\).
The first line of each test case contains \(N\).
The second line of each test case contains \(N\) space-separated integers
\(a_1, a_2, \ldots, a_N\).
It is guaranteed that the sum of \(N\) over all test cases does not exceed \(10^6\).
For each test case, output the lexicographically greatest \(b\) on a new line.
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
평가 및 의견
The Best Lineup
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
The Best Lineup