레이팅 미적용\(1\dots N\) (\(1\le N\le 2\cdot 10^5\))의 순열 \(p_1,p_2,\dots,p_N\)에 대해 \(f(p)=\sum_{i=1}^N \frac{|p_i-i|}{2}\)라 하자. 어떤 순열이 인접한 원소의 교환을 최대 \(f(p)\)번 사용하여 항등 순열로 만들 수 있으면 그 순열을 좋다고 한다.
순열이 주어졌을 때, 그 순열의 순환 이동 중 어떤 것들이 좋은지 구하시오.
문제 제공: Akshaj Arora
채점 방식
- 입력 2: \(N\le 10\)
- 입력 3-5: \(T\le 10, N\le 2000\)
- 입력 6-11: 추가 제약 조건이 없다.
문제 제공: Akshaj Arora
입력은 \(T\) (\(1\le T\le 10^5\))개의 독립적인 테스트로 구성된다. 각 테스트는 다음과 같이 주어진다.
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 \(p_1,p_2,\dots,p_N\) (\(1\le p_i\le N\))이 주어지며, 이는 \(1\dots N\)의 순열임이 보장된다.
모든 테스트에 대한 \(N\)의 합은 \(10^6\)을 넘지 않음이 보장된다.
각 테스트마다 두 줄을 출력한다.
첫째 줄에 좋은 순환 이동의 개수 \(k\)를 출력한다.
그다음 줄에 \(k\)개의 정수 \(s\) (\(0\le s
3
5
5 4 3 2 1
4
1 2 4 3
5
1 2 3 4 50
2
0 1
5
0 1 2 3 4Consider the second test case, where \(p = [1, 2, 4, 3]\).
- \(f(p) = (|1 - 1| + |2 - 2| + |4 - 3| + |3 - 4|) / 2 = 1\). Since \(p\) can be turned into the identity permutation in one move by swapping \(p_3\) and \(p_4\), \(p\) is good.
- Cyclically shifting \(p\) to the right \(1\) time, we get \(q = [3, 1, 2, 4]\). \(f(q) = (|3 - 1| + |1 - 2| + |2 - 3| + |4 - 4|) / 2 = 2\). Since \(q\) can be turned into the identity permutation in two moves by swapping \(q_1\) two steps forward, \(q\) is good.
It can be seen that the other two cyclic shifts are not good.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Third Contest > Gold