Submission #674439

#	Time	Username	Problem	Language	Result	Execution time	Memory
674439		QwertyPi	Cat (info1cup19_cat)	C++14	50 / 100	1082 ms	12868 KiB

cat

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

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

vector<pair<int, int>> ans;
void f(int i, int j){
	ans.push_back({i, 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(){
	ans.clear();
	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();
		ans.push_back({v1, v2});
		ans.push_back({v1, n + 1 - v2});
	}

	cout << ans.size() << ' ' << ans.size() << endl;
	for(auto i : ans){
		cout << i.first << ' ' << i.second << 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