Submission #482736

#	Time	Username	Problem	Language	Result	Execution time	Memory
482736		rk42745417	Cat (info1cup19_cat)	C++17	51.25 / 100	699 ms	15916 KiB

cat

#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
• Subtask 2: 10 / 10
• Subtask 3: 8.75 / 25
• Subtask 4: 15 / 15
• Subtask 5: 12.25 / 35