oj.uz

Submission #674441

# Submission time Handle Problem Language Result Execution time Memory
674441 2022-12-24T08:27:40 Z QwertyPi Cat (info1cup19_cat) C++14
100 / 100
 403 ms 29224 KB 
#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.0 / 15.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 468 KB Output is correct
2 Correct 18 ms 500 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 18 ms 468 KB Output is correct
3 Correct 18 ms 500 KB Output is correct
4 Correct 19 ms 596 KB Output is correct
5 Correct 7 ms 468 KB Output is correct
6 Correct 11 ms 468 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 468 KB Output is correct
2 Correct 18 ms 500 KB Output is correct
3 Correct 377 ms 17632 KB Output is correct
4 Correct 355 ms 26956 KB Output is correct
5 Correct 388 ms 29224 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 18 ms 468 KB Output is correct
3 Correct 18 ms 500 KB Output is correct
4 Correct 19 ms 596 KB Output is correct
5 Correct 7 ms 468 KB Output is correct
6 Correct 11 ms 468 KB Output is correct
7 Correct 377 ms 17632 KB Output is correct
8 Correct 355 ms 26956 KB Output is correct
9 Correct 388 ms 29224 KB Output is correct
10 Correct 383 ms 24992 KB Output is correct
11 Correct 348 ms 23392 KB Output is correct
12 Correct 367 ms 27948 KB Output is correct
13 Correct 403 ms 29004 KB Output is correct
14 Correct 363 ms 27420 KB Output is correct