| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 365353 |
2021-02-11T14:02:12 Z |
Mlxa |
Cat (info1cup19_cat) |
C++14 |
|
1000 ms |
16364 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 = 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)) {
lst.push_back(v);
continue;
}
--in[u];
assert(in[u] >= 0);
preswap(v, u);
int w = p[n - 1 - u];
if (!bad(w)) {
continue;
}
--in[w];
assert(in[w] >= 0);
if (in[w] == 0) {
l.insert(w);
}
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
16364 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
8684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
16364 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
8684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
16364 KB |
Execution killed with signal 6 |
