oj.uz

Submission #522292

# Submission time Handle Problem Language Result Execution time Memory
522292 2022-02-04T13:57:41 Z amunduzbaev Cat (info1cup19_cat) C++17
51.25 / 100
 481 ms 13948 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;

void solve(){
	int n; cin>>n;
	vector<int> a(n), pos(n);
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++) pos[--a[i]] = i;
	vector<ar<int, 2>> res;
	
	auto add = [&](int i, int j){
		int i_ = n - i - 1, j_ = n - j - 1;
		assert(j != i_);
		swap(a[i], a[j]);
		swap(pos[a[i]], pos[a[j]]);
		res.push_back({i, j});
		swap(a[i_], a[j_]);
		swap(pos[a[i_]], pos[a[j_]]);
	};
	//~ int cnt = 0;
	
	for(int i=0;i<n/2;i++){
		if(a[i] == i){
			if(a[n - i - 1] != n - i - 1) { cout<<-1<<"\n"; return; }
			continue;
		}
		int j = pos[i];
		if(j < n/2){
			add(i, j);
		} else {
			if(n - j - 1 < i){
				cout<<-1<<"\n";
				return;
			}
			
			if(n - j - 1 == i){
				if(i + 1 == j){
					cout<<-1<<"\n";
					return;
				}
				
				add(i, i + 1);
				add(i, pos[i]);
			} else {
				add(i, j);
			}
		}
		if(a[n - i - 1] != n - i - 1) { cout<<-1<<"\n"; return; }
	}
	
	cout<<(int)res.size()<<" "<<(int)res.size()<<"\n";
	for(auto x : res) cout<<x[0] + 1<<" "<<x[1] + 1<<"\n";
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int t; cin>>t;
	while(t--){
		solve();
	}
}

/*

10
4 9 6 3 1 ' 10 8 5 2 7
1 9 6 3 4 ' 7 8 5 2 10
1 2 3 4 5 ' 6 7 8 9 10

6
2 6 4 ' 3 1 5
1 2 3 ' 4 5 6

*/

Subtask #1
5.25 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 332 KB Valid reconstruction

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 460 KB Output is correct
2 Correct 17 ms 440 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 332 KB Valid reconstruction
2 Correct 17 ms 460 KB Output is correct
3 Correct 17 ms 440 KB Output is correct
4 Partially correct 21 ms 576 KB Valid reconstruction
5 Partially correct 8 ms 460 KB Valid reconstruction
6 Partially correct 10 ms 332 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 460 KB Output is correct
2 Correct 17 ms 440 KB Output is correct
3 Correct 414 ms 12744 KB Output is correct
4 Correct 376 ms 11600 KB Output is correct
5 Correct 405 ms 13840 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 332 KB Valid reconstruction
2 Correct 17 ms 460 KB Output is correct
3 Correct 17 ms 440 KB Output is correct
4 Partially correct 21 ms 576 KB Valid reconstruction
5 Partially correct 8 ms 460 KB Valid reconstruction
6 Partially correct 10 ms 332 KB Valid reconstruction
7 Correct 414 ms 12744 KB Output is correct
8 Correct 376 ms 11600 KB Output is correct
9 Correct 405 ms 13840 KB Output is correct
10 Partially correct 414 ms 11412 KB Valid reconstruction
11 Partially correct 384 ms 9384 KB Valid reconstruction
12 Partially correct 382 ms 12100 KB Valid reconstruction
13 Partially correct 481 ms 13948 KB Valid reconstruction
14 Partially correct 390 ms 11544 KB Valid reconstruction