이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <cassert>
#include <vector>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> p(n);
for (int i = 0; i < n; ++i)
cin >> p[i], --p[i];
for (int i = 0; i < n; ++i) if (p[i] + p[n - i - 1] != n - 1) {
cout << "-1\n";
return;
}
int e1 = 0;
for (int i = 0; i < n / 2; ++i)
e1 += p[i] >= n / 2;
if (e1 % 2) {
cout << "-1\n";
return;
}
vector<int> rp(n);
for (int i = 0; i < n; ++i)
rp[p[i]] = i;
vector<int> pcp(n / 2);
vector<bool> pcp_leap(n / 2);
for (int i = 0; i < n / 2; ++i) {
if (p[i] < n / 2) {
pcp[i] = p[i];
pcp_leap[i] = 0;
} else {
pcp[i] = n - 1 - p[i];
pcp_leap[i] = 1;
}
}
vector<int> singles;
vector<pair<int, int>> ans;
for (int i = 0; i < n / 2; ++i) {
if (p[i] == i)
continue;
if (pcp[i] == i) {
singles.push_back(i);
continue;
}
vector<int> a;
int j = i;
do {
a.push_back(j);
j = pcp[j];
} while (j != i);
bool xr = false;
for (auto t : a)
xr ^= pcp_leap[t];
if (xr) {
a.clear();
j = i;
do {
a.push_back(j);
j = p[j];
} while (j != i);
//for (auto x : a)
//cout << x << ' ';
//cout << " | " << xr << endl;
for (size_t r = 0; r + 1 < a.size(); ++r) if (a[r + 1] + a[0] == n - 1) {
ans.push_back({a[0], a[r]});
swap(p[a[0]], p[a[r]]);
swap(p[n - 1 - a[0]], p[n - 1 - a[r]]);
singles.push_back(a[0]);
for (size_t t = 2; t <= r; ++t) {
ans.push_back({a[1], a[t]});
swap(p[a[1]], p[a[t]]);
swap(p[n - 1 - a[1]], p[n - 1 - a[t]]);
}
break;
}
} else {
for (size_t t = 0; t + 1 < a.size(); ++t) {
int i0 = a[t];
if (xr)
i0 = n - 1 - a[t];
int j0 = a[t + 1];
xr ^= pcp_leap[a[t + 1]];
if (xr)
j0 = n - 1 - a[t + 1];
ans.push_back({i0, j0});
swap(p[i0], p[j0]);
swap(p[n - 1 - i0], p[n - 1 - j0]);
}
}
}
while (singles.size()) {
int i = singles.back();
singles.pop_back();
int j = singles.back();
singles.pop_back();
ans.push_back({i, n - 1 - j});
swap(p[i], p[n - 1 - j]);
swap(p[n - 1 - i], p[j]);
ans.push_back({i, j});
swap(p[i], p[j]);
swap(p[n - 1 - i], p[n - 1 - j]);
//cout << "{ " << i << ' ' << j << " }" << endl;
}
//if (e1 == 0) {
//vector<int> p0(n / 2);
//for (int i = 0; i < n / 2; ++i)
//p0[i] = p[i];
cout << ans.size() << ' ' << ans.size() << '\n';
for (auto x : ans)
cout << x.first + 1 << ' ' << x.second + 1 << '\n';
//return;
//}
//cout << "1 1\n";
//cout << "1 2\n";
//for (int i = 0; i < n; ++i)
//cout << p[i] << ' ';
//cout << endl << endl;;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
//cout << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |