oj.uz

Submission #674438

# Submission time Handle Problem Language Result Execution time Memory
674438 2022-12-24T08:23:15 Z QwertyPi Cat (info1cup19_cat) C++14
50 / 100
 1000 ms 16708 KB 
#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(){
	int t; cin >> t;
	while(t--) solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 404 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 964 KB Output is correct
2 Correct 88 ms 1004 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 404 KB Output is correct
2 Correct 84 ms 964 KB Output is correct
3 Correct 88 ms 1004 KB Output is correct
4 Correct 100 ms 984 KB Output is correct
5 Correct 36 ms 584 KB Output is correct
6 Correct 28 ms 520 KB Output is correct

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 964 KB Output is correct
2 Correct 88 ms 1004 KB Output is correct
3 Execution timed out 1089 ms 16708 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 404 KB Output is correct
2 Correct 84 ms 964 KB Output is correct
3 Correct 88 ms 1004 KB Output is correct
4 Correct 100 ms 984 KB Output is correct
5 Correct 36 ms 584 KB Output is correct
6 Correct 28 ms 520 KB Output is correct
7 Execution timed out 1089 ms 16708 KB Time limit exceeded
8 Halted 0 ms 0 KB -