oj.uz

Submission #522288

# Submission time Handle Problem Language Result Execution time Memory
522288 2022-02-04T13:38:07 Z amunduzbaev Cat (info1cup19_cat) C++17
51.25 / 100
 454 ms 28488 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);
	for(int i=0;i<n;i++) cin>>a[i];
	vector<int> pos(n);
	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_]]);
	};
	
	for(int i=0;i<n/2;i++){
		if(a[i] == i) 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);
			}
		}
	}
	
	for(int i=1;i<n;i++){
		if(a[i] < a[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 24 ms 544 KB Output is correct
2 Correct 18 ms 956 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 24 ms 544 KB Output is correct
3 Correct 18 ms 956 KB Output is correct
4 Partially correct 22 ms 1092 KB Valid reconstruction
5 Partially correct 9 ms 652 KB Valid reconstruction
6 Partially correct 7 ms 460 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 544 KB Output is correct
2 Correct 18 ms 956 KB Output is correct
3 Correct 438 ms 27700 KB Output is correct
4 Correct 421 ms 25464 KB Output is correct
5 Correct 448 ms 28440 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 24 ms 544 KB Output is correct
3 Correct 18 ms 956 KB Output is correct
4 Partially correct 22 ms 1092 KB Valid reconstruction
5 Partially correct 9 ms 652 KB Valid reconstruction
6 Partially correct 7 ms 460 KB Valid reconstruction
7 Correct 438 ms 27700 KB Output is correct
8 Correct 421 ms 25464 KB Output is correct
9 Correct 448 ms 28440 KB Output is correct
10 Partially correct 422 ms 25036 KB Valid reconstruction
11 Partially correct 427 ms 23440 KB Valid reconstruction
12 Partially correct 454 ms 27376 KB Valid reconstruction
13 Partially correct 449 ms 28488 KB Valid reconstruction
14 Partially correct 440 ms 26784 KB Valid reconstruction