oj.uz

Submission #482740

# Submission time Handle Problem Language Result Execution time Memory
482740 2021-10-26T07:38:14 Z rk42745417 Cat (info1cup19_cat) C++17
100 / 100
 408 ms 13836 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);
		vector<pair<int, int>> ans;
		int tag = -1;
		for(int i = 0; i < n / 2; i++) {
			pos[abs(owo[i])] = i;
		}

		for(int i = 0; i < n / 2; i++) {
			if(pos[i + 1] == i) {
				if(owo[i] < 0) {
					if(tag == -1)
						tag = i;
					else {
						ans.push_back({i, tag});
						ans.push_back({i, n - tag - 1});
						owo[i] *= -1;
						owo[tag] *= -1;
						tag = -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
15.0 / 15.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 17 ms 452 KB Output is correct
3 Correct 17 ms 520 KB Output is correct
4 Correct 18 ms 612 KB Output is correct
5 Correct 7 ms 460 KB Output is correct
6 Correct 6 ms 412 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 452 KB Output is correct
2 Correct 17 ms 520 KB Output is correct
3 Correct 387 ms 12836 KB Output is correct
4 Correct 360 ms 11660 KB Output is correct
5 Correct 383 ms 13836 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 17 ms 452 KB Output is correct
3 Correct 17 ms 520 KB Output is correct
4 Correct 18 ms 612 KB Output is correct
5 Correct 7 ms 460 KB Output is correct
6 Correct 6 ms 412 KB Output is correct
7 Correct 387 ms 12836 KB Output is correct
8 Correct 360 ms 11660 KB Output is correct
9 Correct 383 ms 13836 KB Output is correct
10 Correct 363 ms 11504 KB Output is correct
11 Correct 331 ms 9392 KB Output is correct
12 Correct 371 ms 11016 KB Output is correct
13 Correct 408 ms 13660 KB Output is correct
14 Correct 379 ms 11352 KB Output is correct