Submission #674441

#	Time	Username	Problem	Language	Result	Execution time	Memory
674441		QwertyPi	Cat (info1cup19_cat)	C++14	100 / 100	403 ms	29224 KiB

cat

#include <bits/stdc++.h>
using namespace std;

int a[200001];
int b[200001];
int n;

int ans[200001][2], av = 0;
int o[200001], on = 0;
void f(int i, int j){
	ans[av][0] = i, ans[av++][1] = j;
	swap(a[i], a[j]);
	swap(b[a[i]], b[a[j]]);
	swap(a[n + 1 - i], a[n + 1 - j]);
	swap(b[a[n + 1 - i]], b[a[n + 1 - j]]);
}

void solve(){
	av = on = 0;
	cin >> n; for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n / 2; i++){
		if(a[i] + a[n + 1 - i] != n + 1){
			cout << -1 << endl;
			return;
		}
	}
	for(int i = 1; i <= n; i++) b[a[i]] = i;
	for(int i = 1; i <= n / 2; i++){
		if(a[i] == i) continue;
		else if(a[i] == n + 1 - i) o[on++] = i;
		else f(i, b[i]);
	}

	if(on % 2){
		cout << -1 << endl;
		return;
	}
	
	while(on >= 2){
		int v1 = o[--on], v2 = o[--on];
		f(v1, v2); f(v1, n + 1 - v2);
	}

	cout << av << ' ' << av << '\n';
	for(int i = 0; i < av; i++){
		cout << ans[i][0] << ' ' << ans[i][1] << '\n';
	}
}

int main(){
	cin.tie(0); cout.tie(0)->sync_with_stdio(false);
	int t; cin >> t;
	while(t--) solve();
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15
• Subtask 5: 35 / 35