oj.uz

Submission #482733

# Submission time Handle Problem Language Result Execution time Memory
482733 2021-10-26T07:24:55 Z rk42745417 Cat (info1cup19_cat) C++17
25 / 100
 420 ms 13948 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;
					if(owo[i] > 0)
						neg.erase(g);
					else
						neg.insert(g);
					if(owo[g] < 0)
						neg.insert(i);
					else
						neg.erase(i);
				}
				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
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 332 KB Given positions are equal

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 460 KB Output is correct
2 Correct 18 ms 460 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 332 KB Given positions are equal

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 460 KB Output is correct
2 Correct 18 ms 460 KB Output is correct
3 Correct 419 ms 12752 KB Output is correct
4 Correct 420 ms 11552 KB Output is correct
5 Correct 418 ms 13948 KB Output is correct

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 332 KB Given positions are equal