레이팅 미적용농부 존은 \(N\)개의 정수를 담은 배열 \(A\)를 가지고 있다 (\(1 \leq N \leq 5 \cdot 10^5, 1 \leq A_i \leq N\)). 그는 가장 좋아하는 인덱스 \(j\)를 고르고 \(A_j\)만 적혀 있는 종이 한 장을 꺼낸다. 그런 다음 다음 연산을 몇 번이든 수행할 수 있다.
- \(A\)의 모든 원소를 왼쪽으로 한 칸 또는 오른쪽으로 한 칸 순환 이동한다. 그런 다음 종이에 \(A_j\)를 적는다.
\(A\)에 나타나는 서로 다른 정수들의 집합을 \(S\)라 하자. 농부 존은 종이에 \(S\)에 나타나는 모든 정수가 적히도록 하기 위해 수행해야 하는 연산의 최소 횟수가 궁금하다.
농부 존이 가장 좋아하는 인덱스가 무엇인지 알 수 없으므로, 가능한 모든 인덱스 \(1 \leq j \leq N\)에 대한 답을 출력하라. 각 인덱스에 대해, 연산을 수행하기 전에 \(A\)는 원래 형태로 초기화됨에 유의하라.
Problem credits: Chongtian Ma
SCORING
- 입력 3-5: \(N\le 500\)
- 입력 6-8: \(N\le 10^4\)
- 입력 9-17: 추가 제약 없음.
Problem credits: Chongtian Ma
첫째 줄에 \(N\)이 주어진다.
다음 줄에 \(A_1, A_2, \ldots, A_N\)이 주어진다.
공백으로 구분된 \(N\)개의 정수를 출력하며, \(i\)번째 정수는 가장 좋아하는 인덱스가 \(j = i\)일 때의 답이다.
6
1 2 3 1 3 44 3 3 4 3 3The distinct numbers are \(S = \{ 1, 2, 3, 4 \}\). Suppose Farmer John’s
favorite index is \(j=1\). He starts off with \(A_1=1\) written on a piece of paper.
We can track the array \(A\) after each cyclic shift Farmer John makes.
- Cyclic shift right: FJ writes down \(A_1 = 4\).
4 1 2 3 1 3
- Cyclic shift left: FJ writes down \(A_1 = 1\) again.
1 2 3 1 3 4
- Cyclic shift left: FJ writes down \(A_1 = 2\).
2 3 1 3 4 1
- Cyclic shift left: FJ writes down \(A_1 = 3\).
3 1 3 4 1 2
At this point, Farmer John has written down every number in \(S\) using 4
operations.
12
1 1 2 1 1 3 1 1 4 1 1 18 7 6 7 8 9 8 7 6 7 8 9riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Second Contest > Silver