Majority Opinion
골드 V의견: 0
Farmer John has an important task - figuring out what type of hay to buy for his
cows.
Farmer John's \(N\) cows (\(2 \le N \le 10^5\)) are numbered \(1\) through \(N\) and
each cow likes exactly one type of hay \(h_i\) (\(1 \le h_i \le N\)). He wants all
his cows to like the same type of hay.
To make this happen, Farmer John can host focus groups. A focus group consists
of getting all cows in a contiguous range numbered \(i\) to \(j\), inclusive,
together for a meeting. If there is a type of hay that more than half the cows
in the group like, then after the focus group finishes meeting, all cows end up
liking that type of hay. If no such type of hay exists, then no cows change the
type of hay they like. For example, in focus group consisting of a range of 16
cows, 9 or more of them would need to have the same hay preference to cause the
remaining cows to switch their preference to match.
Farmer John wants to know which types of hay can become liked by all cows
simultaneously. He can only host one focus group at a time, but he can run as
many focus groups as necessary to get all cows to like the same type of hay.
Problem credits: Nick Wu
SCORING
- Input 2: \(N = 2\).
- Inputs 3-4: \(N \le 50\).
- Inputs 5-6: \(h_i \le h_{i+1}\) for all \(1 \le i \le N-1\).
- Inputs 7-15: No additional constraints.
Problem credits: Nick Wu
The first will consist of an integer \(T\), denoting the number of independent
test cases \((1 \leq T \leq 10)\).
The first line of each test case consists of \(N\).
The second line consists of \(N\) integers, the favorite types of hay \(h_i\) for
the cows in order.
It is guaranteed that the sum of \(N\) over all test cases does not exceed
\(2\cdot 10^5\).
Output \(T\) lines, one line per test case.
If it possible to make all cows like the same type of hay simultaneously, output
all possible such types of hay in increasing order. Otherwise, output \(-1\).
When printing a list of numbers on the same line, separate adjacent numbers with
a space, and be sure the line does not end with any extraneous spaces.
5
5
1 2 2 2 3
6
1 2 3 1 2 3
6
1 1 1 2 2 2
3
3 2 3
2
2 12
-1
1 2
3
-1In the sample input, there are 5 test cases.
In the first test case, it is only possible to make all cows like type 2. FJ can
do this by running a single focus group with all cows.
In the second test case, we can show that no cows will change which type of hay
they like.
In the third test case, it is possible to make all cows like type 1 by running
three focus groups - first by having cows 1 through 4 in a focus group, then by
having cows 1 through 5 in a focus group, then by having cows 1 through 6 in a
focus group. By similar logic, using cows 3 through 6, cows 2 through 6, then
cows 1 through 6, we can make all cows like type 2.
In the fourth test case, it is possible to make all cows like type 3 by running
a single focus group with all cows.
In the fifth test case, we can show that no cows will change which type of hay
they like.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > January > Bronze
평가 및 의견
Majority Opinion
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Majority Opinion