Submission #365359

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
365359	2021-02-11T14:13:31 Z	Mlxa	Cat (info1cup19_cat)	C++14	0 / 100	1000 ms	8428 KB

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 = 1e6 + 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() {
	fill_n(in, N, 0);
	answer.clear();

	cin >> n;
	assert(n % 2 == 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 (!bad(j)) {
			continue;
		}
		// cout << i << " -> " << j << endl;
		if (i == j) {
			continue;
		}
		if (p[n - 1 - j] == i) {
			preswap(i, j);
		} else {
			edge(i, j);
		}
	}
	set<int> l;
	for (int i = 0; i < n - 1 - i; ++i) {
		if (bad(i) && !in[i]) {
			l.insert(i);
		}
	}
	vector<int> lst;
	while (l.size()) {
		int v = *l.begin();
		l.erase(v);
		int u = p[n - 1 - v];
		if (v == u || !bad(u)) {
			continue;
		}
		int w = p[n - 1 - u];
		--in[u];
		assert(in[u] >= 0);
		preswap(v, u);
		if (!bad(w)) {
			continue;
		}
		--in[w];
		assert(in[w] >= 0);
		if (in[w] == 0) {
			l.insert(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) {
		assert(p[i] < p[n - 1 - i]);
	}
	for (int i = 0; i < n - 1 - i; ++i) {
		while (p[i] != i) {
			go(i, p[i]);
		}
	}
	assert(is_sorted(p, p + n));
	cout << answer.size() << " " << answer.size() << "\n";
	for (auto e : answer) {
		cout << e.x << " " << e.y << endl;
	}
#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));
#endif
    ios::sync_with_stdio(0); cin.tie(0);
    int tn;
    cin >> tn;
    while (tn--) {
    	solve();
    }
    return 0;
}

Subtask #1

0.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1091 ms	8300 KB	Time limit exceeded

Subtask #2

0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1093 ms	8428 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1091 ms	8300 KB	Time limit exceeded

Subtask #4

0.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1093 ms	8428 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1091 ms	8300 KB	Time limit exceeded