cf #653 div3 F - Cyclic Shifts Sorting (그리디, constructive, sorting, inversion)

https://codeforces.com/contest/1374/problem/F

소팅 문제에서 inversion개수로 규칙찾기

 

<문제설명>

원소의 수가 n개인 배열 a에서 다음 연산을 최대 $n^2$번 수행하여 정렬하여라. 정렬 못하면 -1 출력

 

<풀이>

1. i번째 원소를 맨 앞으로 가져올 수 있다. 

 

2. a의 원소가 모두 distinct하면 위 operation으로 inversion 개수의 parity를 바꿀 수 없다. 따라서 이 때 inversion 개수의 parity가 홀수면 정렬 불가능하다.

 

3. a의 원소에 중복 원소가 있다면 일단 distinct한 배열로 바꿔준 후에, inversion 개수의 parity가 홀수라면 중복 원소 한 쌍을 swap하여 parity를 짝수로 맞춰주면 된다.

 

예를들어 $a = [2,1,3,3,4]$인 경우 일단 distinct한 배열로 바꿔서 $a=[2,1,3,4,5]$로 만들어 준다.

그 후에 inversion개수 parity가 홀수였으므로 중복원소 쌍 3,3 의 순서를 바꿔준다. $a=[2,4,1,3,5]$

 

그리고 나서 1번 성질을 이용한 sorting을 해주면 된다.

 

<코드>

int n, a[MAX];
P b[MAX];
vector<int> g[MAX];

void shift_(int i) {
	int temp = a[i+2];
	a[i+2] = a[i+1];
	a[i+1] = a[i];
	a[i] = temp;
}

void solve() {
	for (int i = 0; i < MAX; i++) g[i].clear();

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		g[a[i]].push_back(i);
		b[i] = { a[i], i };
	}

	bool flag = 0;
	int inversion = 0;
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			if (a[i] > a[j]) inversion++;

	sort(b + 1, b + n + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 1,x,y; j <= n; j++) {
			tie(x, y) = b[j];
			if (j > 1 && b[j - 1].first == x) flag = 1;
			if (a[i] == x && i == y) a[i] = j;
		}
	}

	if (!flag && inversion%2 != 0) {
		cout << -1 << '\n';
		return;
	}
	if (flag && inversion%2 != 0) {
		for (int i = 1; i < MAX; i++) if (g[i].size() > 1) {
			swap(a[g[i][0]], a[g[i][1]]);
			break;
		}
	}
	vector<int> ans;
	for (int i = 1; i <= n; i++) {
		int pos = 0;
		for (int j = i; j <= n; j++) if (a[j] == i) {
			pos = j;
			break;
		}
		if (pos % 2 == i % 2) {
			while (1) {
				if (pos == i) break;
				pos -= 2;
				ans.push_back(pos);
				shift_(pos);
			}
		}
		else {
			while (1) {
				if (i + 1 == pos) break;
				pos -= 2;
				ans.push_back(pos);
				shift_(pos);
			}
			ans.push_back(pos-1);
			ans.push_back(pos-1);
			shift_(pos - 1);
			shift_(pos - 1);
		}
	}
	cout << ans.size() << '\n';
	for (int i : ans) cout << i << " ";
	cout << '\n';
}

int main() {
	FAST;
	int tt; cin >> tt;
	while (tt--) solve();
}