oj.uz

Submission #482736

# Submission time Handle Problem Language Result Execution time Memory
482736 2021-10-26T07:27:16 Z rk42745417 Cat (info1cup19_cat) C++17
51.25 / 100
 699 ms 15916 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;
		set<int> neg;
		for(int i = 0; i < n / 2; i++) {
			if(owo[i] < 0)
				neg.insert(i);
			pos[abs(owo[i])] = i;
		}

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

		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 18 ms 516 KB Output is correct
2 Correct 18 ms 532 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 18 ms 516 KB Output is correct
3 Correct 18 ms 532 KB Output is correct
4 Partially correct 27 ms 524 KB Valid reconstruction
5 Partially correct 15 ms 460 KB Valid reconstruction
6 Partially correct 8 ms 332 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 516 KB Output is correct
2 Correct 18 ms 532 KB Output is correct
3 Correct 386 ms 12772 KB Output is correct
4 Correct 385 ms 11592 KB Output is correct
5 Correct 437 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 18 ms 516 KB Output is correct
3 Correct 18 ms 532 KB Output is correct
4 Partially correct 27 ms 524 KB Valid reconstruction
5 Partially correct 15 ms 460 KB Valid reconstruction
6 Partially correct 8 ms 332 KB Valid reconstruction
7 Correct 386 ms 12772 KB Output is correct
8 Correct 385 ms 11592 KB Output is correct
9 Correct 437 ms 13840 KB Output is correct
10 Partially correct 615 ms 11952 KB Valid reconstruction
11 Partially correct 545 ms 10024 KB Valid reconstruction
12 Partially correct 582 ms 14248 KB Valid reconstruction
13 Partially correct 699 ms 15916 KB Valid reconstruction
14 Partially correct 594 ms 13164 KB Valid reconstruction