Good Cyclic Shifts
골드 II의견: 0
For a permutation \(p_1,p_2,\dots,p_N\) of \(1\dots N\) (\(1\le N\le 2\cdot 10^5\)),
let \(f(p)=\sum_{i=1}^N \frac{|p_i-i|}{2}\). A permutation is
good
if it can be turned into the identity permutation using at most \(f(p)\) swaps of
adjacent elements.
Given a permutation, find which cyclic shifts of it are good.
Problem credits: Akshaj Arora
SCORING
- Input 2: \(N\le 10\)
- Inputs 3-5: \(T\le 10, N\le 2000\)
- Inputs 6-11: No additional constraints.
Problem credits: Akshaj Arora
The input consists of \(T\) (\(1\le T\le 10^5\)) independent tests. Each test is
specified as follows:
The first line contains \(N\).
The second line contains \(p_1,p_2,\dots,p_N\) (\(1\le p_i\le N\)), which is
guaranteed to be a permutation of \(1\dots N\).
It is guaranteed that the sum of \(N\) over all tests does not exceed \(10^6\).
For each test, output two lines:
On the first line, output the number of good cyclic shifts \(k\).
Then output a line with \(k\) space-separated integers \(s\) (\(0\le s
increasing order, meaning that \(p\) is good when cyclically shifted to the right
\(s\) times.
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
평가 및 의견
Good Cyclic Shifts
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Good Cyclic Shifts