Submission #365366

#TimeUsernameProblemLanguageResultExecution timeMemory
365366MlxaCat (info1cup19_cat)C++14
25 / 100
28 ms1132 KiB
#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 = 1e2 + 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 (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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...