RiseOJ – 다수 의견

설명

농부 존에게 중요한 일이 생겼다. 바로 소들에게 어떤 종류의 건초를 사 줄지 정하는 일이다.

농부 존의 소 $$N$$ 마리 ( $2 \le N \le 10^5$ )는 $$1$$ 번부터 $$N$$ 번까지 번호가 붙어 있고, 각 소는 정확히 한 종류의 건초 $$h_i$$ 를 좋아한다 ( $1 \le h_i \le N$ ). 존은 모든 소가 같은 종류의 건초를 좋아하게 만들고 싶다.

이를 위해 농부 존은 포커스 그룹을 열 수 있다. 포커스 그룹이란 번호가 $$i$$ 부터 $$j$$ 까지(양 끝 포함)인 연속 구간의 소들을 모두 모아 회의를 하는 것이다. 그룹에 속한 소의 절반보다 많은 소가 좋아하는 건초 종류가 존재하면, 포커스 그룹 회의가 끝난 뒤 모든 소가 그 종류의 건초를 좋아하게 된다. 그런 건초 종류가 없으면 어떤 소도 좋아하는 건초를 바꾸지 않는다. 예를 들어 소 16마리로 이루어진 구간의 포커스 그룹에서는, 9마리 이상이 같은 건초를 좋아해야 나머지 소들이 그에 맞춰 선호를 바꾼다.

농부 존은 어떤 종류의 건초가 모든 소에게 동시에 사랑받을 수 있는지 알고 싶다. 포커스 그룹은 한 번에 하나씩만 열 수 있지만, 모든 소가 같은 건초를 좋아하게 될 때까지 필요한 만큼 여러 번 열 수 있다.

출제: Nick Wu

제약

배점

입력 2: $$N = 2$$ .
입력 3-4: $N \le 50$ .
입력 5-6: 모든 $1 \le i \le N-1$ 에 대해 $h_i \le h_{i+1}$ .
입력 7-15: 추가 제약 없음.

출제: Nick Wu

입력 형식

첫째 줄에 독립적인 테스트 케이스의 개수를 나타내는 정수 $$T$$ 가 주어진다 $(1 \leq T \leq 10)$ .

각 테스트 케이스의 첫째 줄에 $$N$$ 이 주어진다.

둘째 줄에 소들이 좋아하는 건초 종류 $$h_i$$ 가 순서대로 $$N$$ 개 주어진다.

모든 테스트 케이스에 대한 $$N$$ 의 합이 $2\cdot 10^5$ 를 넘지 않음이 보장된다.

출력 형식

$$T$$ 개의 줄을 출력한다. 테스트 케이스마다 한 줄씩 출력한다.

모든 소가 동시에 같은 종류의 건초를 좋아하게 만들 수 있다면, 가능한 모든 건초 종류를 증가하는 순서로 출력한다. 불가능하다면 $$-1$$ 을 출력한다. 한 줄에 여러 수를 출력할 때는 인접한 수를 공백 하나로 구분하고, 줄 끝에 불필요한 공백이 없도록 한다.

예제 1

입력

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 1

출력

설명

In 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

올림피아드 > USACO > 2023-2024 > January > Bronze

태그

JudgeUSACO

다수 의견

평가 및 의견

풀이 제출