#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
#undef KEV
#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 debug(...) 0
#endif
const int MAX_N = 3000010;
int per[MAX_N], n, pos[MAX_N], ma[MAX_N], cp[MAX_N];
void fail() {
puts("-1"), exit(0);
}
void sw(int a, int b) {
swap(per[a], per[b]);
swap(pos[per[a]], pos[per[b]]);
}
int rev(int i) {
return n - i + 1;
}
vector< pair<int,int> > res;
bool part() {
vector<int> L, R;
int m = n / 2;
for (int i = 1;i <= m;++i)
if (per[i] > m)
L.pb(i);
for (int i = m+1;i <= n;++i)
if (per[i] <= m)
R.pb(i);
assert(L.size() == R.size());
reverse(AI(R));
m = L.size();
if (m&1) return false;
for (int i = 0;i < m;++i)
if (L[i] != rev(R[i]))
return false;
for (int i = 1;i <= n;++i)
cp[i] = per[i];
for (int i = 0;i < m;++i) {
swap(cp[ L[i] ], cp[ R[i] ]);
ma[ L[i] ] = R[i];
}
return true;
}
bool make_match() {
return true;
vector<int> p(cp, cp+n+1);
vector<int> pos(n+1);
for (int i = 1;i <= n;++i)
pos[ cp[i] ] = i;
vector<bool> did(n+1);
int m = n / 2;
auto sw = [&](int a, int b) {
swap(p[a], p[b]);
swap(pos[p[a]], pos[p[b]]);
};
vector<int> O;
auto putin = [&](int x) {
O.pb(x);
};
auto popop = [&]() {
while (O.size() >= 2) {
int y = O.back(); O.pop_back();
int x = O.back(); O.pop_back();
int a = x, b = ma[y], c = y, d = ma[x];
//cerr << "Before swap\n";
::sw(a, b), ::sw(c, d);
res.pb(a, b);
}
};
debug(p.begin()+1, p.begin()+m+1);
for (int i = 1;i <= m;++i) {
if (did[i]) continue;
did[i] = true;
if (ma[i]) putin(i);
while (i != p[i]) {
int x = p[i];
did[x] = true;
if (ma[x]) putin(x);
DE(i, x);
sw(x, i);
}
popop();
}
return O.empty();
}
void solve() {
cin >> n;
for (int i = 1;i <= n;++i)
cin >> per[i], pos[per[i]] = i;
res.clear();
if (!part() || !make_match()) {
cout << -1 << '\n';
return;
}
//cerr << "Per \n";
int m = n / 2;
for (int i = 1;i <= n;++i)
pos[ per[i] ] = i;
for (int i = 1;i <= m;++i) {
while (i != per[i]) {
int x = per[i];
res.pb(i, x);
int a = i, b = x, c = n-a+1, d = n-b+1;
sw(a, b);
sw(c, d);
}
}
//cerr << "swap complete\n";
for (int i = 1;i <= n;++i)
if (i != per[i]) {
cout << -1 << '\n';
return ;
}
cout << res.size() << ' ' << 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();
}
Compilation message
cat.cpp: In function 'bool make_match()':
cat.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 0
| ^
cat.cpp:82:2: note: in expansion of macro 'debug'
82 | debug(p.begin()+1, p.begin()+m+1);
| ^~~~~
cat.cpp:13:17: warning: statement has no effect [-Wunused-value]
13 | #define DE(...) 0
| ^
cat.cpp:91:4: note: in expansion of macro 'DE'
91 | DE(i, x);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
544 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
512 KB |
Output is correct |
| 2 |
Correct |
22 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
544 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
512 KB |
Output is correct |
| 2 |
Correct |
22 ms |
512 KB |
Output is correct |
| 3 |
Correct |
516 ms |
10936 KB |
Output is correct |
| 4 |
Correct |
502 ms |
10480 KB |
Output is correct |
| 5 |
Correct |
536 ms |
13036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
544 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
