oj.uz

Submission #674440

# Submission time Handle Problem Language Result Execution time Memory
674440 2022-12-24T08:26:03 Z QwertyPi Cat (info1cup19_cat) C++14
50 / 100
 1000 ms 9572 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 592 KB Output is correct
2 Correct 64 ms 556 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 340 KB Output is correct
2 Correct 68 ms 592 KB Output is correct
3 Correct 64 ms 556 KB Output is correct
4 Correct 81 ms 572 KB Output is correct
5 Correct 32 ms 436 KB Output is correct
6 Correct 24 ms 424 KB Output is correct

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 592 KB Output is correct
2 Correct 64 ms 556 KB Output is correct
3 Execution timed out 1008 ms 9572 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 340 KB Output is correct
2 Correct 68 ms 592 KB Output is correct
3 Correct 64 ms 556 KB Output is correct
4 Correct 81 ms 572 KB Output is correct
5 Correct 32 ms 436 KB Output is correct
6 Correct 24 ms 424 KB Output is correct
7 Execution timed out 1008 ms 9572 KB Time limit exceeded
8 Halted 0 ms 0 KB -