Submission #365367

#	Time	Username	Problem	Language	Result	Execution time	Memory
365367		Mlxa	Cat (info1cup19_cat)	C++14	61 / 100	575 ms	29972 KiB

cat

#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif
using namespace std;
using ll = long long;
#define int ll
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple

const int N = 2e5 + 10;
int n;
int p[N];

bool bad(int i) {
	assert(0 <= i && i < n - 1 - i);
	return p[i] > p[n - 1 - i];
}

int in[N];

void edge(int v, int u) {
	assert(bad(v) && bad(u));
	++in[u];
}

vector<pair<int, int>> answer;

void go(int i, int j) {
	// cout << "go " << i << " " << j << endl;
	answer.emplace_back(i + 1, j + 1);
	swap(p[i], p[j]);
	swap(p[n - 1 - i], p[n - 1 - j]);
}

void preswap(int i, int j) {
	go(i, n - 1 - j);
}

void solve() {
	answer.clear();

	cin >> n;
	fill_n(in, n, 0);
	for (int i = 0; i < n; ++i) {
		cin >> p[i];
		--p[i];
	}
	for (int i = 0; i < n - 1 - i; ++i) {
		if (p[i] + p[n - 1 - i] != n - 1) {
			cout << "-1\n";
			return;
		}
	}
	for (int i = 0; i < n - 1 - i; ++i) {
		if (!bad(i)) {
			continue;
		}
		int j = p[n - 1 - i];
		if (i == j || !bad(j)) {
			continue;
		}
		if (p[n - 1 - j] == i) {
			preswap(i, j);
		} else {
			edge(i, j);
		}
	}
	queue<int> l;
	for (int i = 0; i < n - 1 - i; ++i) {
		if (bad(i) && !in[i]) {
			l.push(i);
		}
	}
	vector<int> lst;
	while (l.size()) {
		int v = l.front(); l.pop();
		int u = p[n - 1 - v];
		if (v == u || !bad(u)) {
			continue;
		}
		int w = p[n - 1 - u];
		--in[u];
		preswap(v, u);
		if (!bad(w)) {
			continue;
		}
		--in[w];
		if (in[w] == 0) {
			l.push(w);
		}
	}
	for (int i = 0; i < n - 1 - i; ++i) {
		if (bad(i) && p[n - 1 - i] != i && bad(p[n - 1 - i])) {
			preswap(i, p[n - 1 - i]);
		}
	}
	for (int i = 0; i < n - 1 - i; ++i) {
		if (bad(i)) {
			lst.push_back(i);
		}
	}
	if (lst.size() % 2) {
		cout << "-1\n";
		return;
	}
	for (int i = 0; i < (int)lst.size(); i += 2) {
		preswap(lst[i], lst[i + 1]);
	}
	for (int i = 0; i < n - 1 - i; ++i) {
		while (p[i] != i) {
			go(i, p[i]);
		}
	}
	cout << answer.size() << " " << answer.size() << "\n";
	for (auto e : answer) {
		cout << e.x << " " << e.y << "\n";
	}
#ifdef LC
	cout << endl;
#endif
	// for (int i = 0; i < n; ++i) {
	// 	cout << p[i] << " ";
	// }
	// cout << endl;
}

signed main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
    assert(freopen("output.txt", "w", stdout));
#endif
    ios::sync_with_stdio(0); cin.tie(0);
    int tn;
    cin >> tn;
    while (tn--) {
    	solve();
    }
#ifdef LC
    cerr << 1000 * clock() / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 8.75 / 25
• Subtask 4: 15 / 15
• Subtask 5: 12.25 / 35