제출 #674440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
674440		QwertyPi	Cat (info1cup19_cat)	C++14	50 / 100	1008 ms	9572 KiB

cat

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

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

int ans[200001][2], av = 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 = 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;
	vector<int> oppo;
	for(int i = 1; i <= n / 2; i++){
		if(a[i] == i) continue;
		else if(a[i] == n + 1 - i) oppo.push_back(i);
		else f(i, b[i]);
	}

	if(oppo.size() % 2){
		cout << -1 << endl;
		return;
	}
	
	while(oppo.size() >= 2){
		int v1 = oppo.back(); oppo.pop_back();
		int v2 = oppo.back(); oppo.pop_back();
		f(v1, v2); f(v1, n + 1 - v2);
	}

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

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: 0 / 15
• Subtask 5: 0 / 35