oj.uz

Submission #482732

# Submission time Handle Problem Language Result Execution time Memory
482732 2021-10-26T07:12:40 Z rk42745417 Cat (info1cup19_cat) C++17
51.25 / 100
 456 ms 13980 KB 
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const ll LINF = ll(2e18) + ll(1e15);
const double EPS = 1e-8;
static auto LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();

signed main() {
	int t;
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		vector<int> arr(n);
		for(int &a : arr)
			cin >> a;
		{
			bool ok = 1;
			int w = 0;
			for(int i = 0; i < n / 2; i++) {
				if(arr[i] + arr[n - i - 1] != n + 1)
					ok = false;
				w += arr[i] > n / 2;
			}
			if(!ok || w % 2) {
				cout << "-1\n";
				continue;
			}
		}
		vector<int> owo(n / 2);
		for(int i = 0; i < n / 2; i++)
			owo[i] = (arr[i] > n / 2 ? -(n + 1 - arr[i]) : arr[i]);
		vector<int> pos(n / 2 + 1);
		for(int i = 0; i < n / 2; i++)
			pos[abs(owo[i])] = i;
		vector<pair<int, int>> ans;

		for(int i = 0; i < n / 2; i++) {
			//cout << "Debug: ";
			//for(int a : owo)
				//cout << a << ' ';
			//cout << '\n';
			if(pos[i + 1] == i) {
				if(owo[i] < 0) {
					ans.push_back({i, i + 1});
					ans.push_back({i, n - (i + 1) - 1});
					owo[i] *= -1;
					owo[i + 1] *= -1;
				}
			}
			else {
				int g = pos[i + 1];
				if(owo[g] < 0) {
					ans.push_back({i, n - g - 1});
					owo[g] *= -1;
					owo[i] *= -1;
				}
				else {
					ans.push_back({i, g});
				}
				swap(pos[i + 1], pos[abs(owo[i])]);
				swap(owo[g], owo[i]);
			}
		}

		cout << ans.size() << ' ' << ans.size() << '\n';
		for(const auto &[a, b] : ans)
			cout << a + 1 << ' ' << b + 1 << '\n';
	}
}

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 528 KB Output is correct
2 Correct 17 ms 508 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 528 KB Output is correct
3 Correct 17 ms 508 KB Output is correct
4 Partially correct 21 ms 588 KB Valid reconstruction
5 Partially correct 8 ms 460 KB Valid reconstruction
6 Partially correct 7 ms 388 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 528 KB Output is correct
2 Correct 17 ms 508 KB Output is correct
3 Correct 456 ms 12840 KB Output is correct
4 Correct 366 ms 11564 KB Output is correct
5 Correct 405 ms 13780 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 528 KB Output is correct
3 Correct 17 ms 508 KB Output is correct
4 Partially correct 21 ms 588 KB Valid reconstruction
5 Partially correct 8 ms 460 KB Valid reconstruction
6 Partially correct 7 ms 388 KB Valid reconstruction
7 Correct 456 ms 12840 KB Output is correct
8 Correct 366 ms 11564 KB Output is correct
9 Correct 405 ms 13780 KB Output is correct
10 Partially correct 394 ms 11768 KB Valid reconstruction
11 Partially correct 445 ms 9692 KB Valid reconstruction
12 Partially correct 382 ms 11172 KB Valid reconstruction
13 Partially correct 437 ms 13980 KB Valid reconstruction
14 Partially correct 430 ms 11500 KB Valid reconstruction