oj.uz

Submission #522289

# Submission time Handle Problem Language Result Execution time Memory
522289 2022-02-04T13:42:07 Z amunduzbaev Cat (info1cup19_cat) C++17
51.25 / 100
 463 ms 14088 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_]]);
	};
	int cnt = 0;
	
	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]);
				cnt++;
			} 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() - cnt<<" "<<(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 4 ms 332 KB Valid reconstruction

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 528 KB Output is correct
2 Correct 35 ms 516 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 332 KB Valid reconstruction
2 Correct 25 ms 528 KB Output is correct
3 Correct 35 ms 516 KB Output is correct
4 Partially correct 28 ms 576 KB Valid reconstruction
5 Partially correct 9 ms 460 KB Valid reconstruction
6 Partially correct 7 ms 332 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 528 KB Output is correct
2 Correct 35 ms 516 KB Output is correct
3 Correct 421 ms 12812 KB Output is correct
4 Correct 418 ms 10656 KB Output is correct
5 Correct 431 ms 14088 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 332 KB Valid reconstruction
2 Correct 25 ms 528 KB Output is correct
3 Correct 35 ms 516 KB Output is correct
4 Partially correct 28 ms 576 KB Valid reconstruction
5 Partially correct 9 ms 460 KB Valid reconstruction
6 Partially correct 7 ms 332 KB Valid reconstruction
7 Correct 421 ms 12812 KB Output is correct
8 Correct 418 ms 10656 KB Output is correct
9 Correct 431 ms 14088 KB Output is correct
10 Partially correct 403 ms 11592 KB Valid reconstruction
11 Partially correct 384 ms 9740 KB Valid reconstruction
12 Partially correct 458 ms 12324 KB Valid reconstruction
13 Partially correct 463 ms 14084 KB Valid reconstruction
14 Partially correct 401 ms 11512 KB Valid reconstruction