oj.uz

Submission #365367

# Submission time Handle Problem Language Result Execution time Memory
365367 2021-02-11T14:18:31 Z Mlxa Cat (info1cup19_cat) C++14
61 / 100
 575 ms 29972 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 556 KB Output is correct
2 Correct 21 ms 620 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 364 KB Output is correct
2 Correct 24 ms 556 KB Output is correct
3 Correct 21 ms 620 KB Output is correct
4 Partially correct 26 ms 620 KB Valid reconstruction
5 Partially correct 10 ms 620 KB Valid reconstruction
6 Partially correct 10 ms 620 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 556 KB Output is correct
2 Correct 21 ms 620 KB Output is correct
3 Correct 497 ms 11880 KB Output is correct
4 Correct 498 ms 11492 KB Output is correct
5 Correct 531 ms 14436 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 364 KB Output is correct
2 Correct 24 ms 556 KB Output is correct
3 Correct 21 ms 620 KB Output is correct
4 Partially correct 26 ms 620 KB Valid reconstruction
5 Partially correct 10 ms 620 KB Valid reconstruction
6 Partially correct 10 ms 620 KB Valid reconstruction
7 Correct 497 ms 11880 KB Output is correct
8 Correct 498 ms 11492 KB Output is correct
9 Correct 531 ms 14436 KB Output is correct
10 Partially correct 575 ms 24168 KB Valid reconstruction
11 Partially correct 575 ms 23012 KB Valid reconstruction
12 Partially correct 522 ms 29676 KB Valid reconstruction
13 Partially correct 574 ms 29972 KB Valid reconstruction
14 Partially correct 525 ms 28948 KB Valid reconstruction