# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
315145 | Kevin_Zhang_TW | Cat (info1cup19_cat) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define deubg(...) 0
#endif
const int MAX_N = 3000010;
int per[MAX_N], n, pos[MAX_N];
void fail() {
puts("-1"), exit(0);
}
void sw(int a, int b) {
DE(a, b, per[a], per[b]);
swap(per[a], per[b]);
swap(pos[per[a]], pos[per[b]]);
}
void solve() {
cin >> n;
for (int i = 1;i <= n;++i)
cin >> per[i], pos[per[i]] = i;
for (int i = 1;i <= n/2;++i)
if (per[i] > n/2) fail();
vector< pair<int,int> > res;
res.reserve(n);
int m = n / 2;
DE(m);
for (int i = 1;i <= m;++i) {
while (i != per[i]) {
int x = per[i];
res.pb(i, pos[i]);
int a = i, b = pos[i], c = n-a+1, d = n-b+1;
sw(a, b);
sw(c, d);
}
}
debug(per+1, per+1+n);
for (int i = 1;i <= n;++i)
if (i != per[i]) {
cout << -1 << '\n';
return;
}
cout << res.size() << '\n';
for (auto [a, b] : res)
cout << a << ' ' << b << '\n';
}
signed main(){
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
solve();
}