Submission #639792

#TimeUsernameProblemLanguageResultExecution timeMemory
639792Dec0DeddCat (info1cup19_cat)C++14
25 / 100
925 ms26664 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e5+1; #define pii pair<int, int> int p[N], x[N], n; vector<pii> v; void swp(int i, int j) { v.push_back({i, j}); swap(p[i], p[j]), swap(x[p[i]], x[p[j]]); swap(p[n-i+1], p[n-j+1]), swap(x[p[n-i+1]], x[p[n-j+1]]); } void solve() { cin>>n; v.clear(); for (int i=1; i<=n; ++i) { cin>>p[i]; x[p[i]]=i; } bool ok=true; for (int i=1; i<=n/2; ++i) { if (p[n-i+1] != n-p[i]+1) ok=false; } int c=0; for (int i=1; i<=n/2; ++i) { if (p[i] > n/2) ++c; } if (!ok || c%2) { cout<<-1<<"\n"; return; } stack<int> s; for (int i=1; i<=n/2; ++i) { if (p[i] <= n/2) continue; int r=n-p[i]+1; if (x[r] > n/2 && x[r] != n-i+1) swp(i, x[r]); else if (x[i] > n/2 && x[i] != n-i+1) swp(i, x[i]); else s.push(i); } assert(s.size()%2 == 0); while (!s.empty()) { int a=s.top(); s.pop(); int b=s.top(); s.pop(); swp(a, n-b+1); } for (int i=1; i<=n/2; ++i) { while (p[i] != i) swp(i, p[i]); } cout<<v.size()<<" "<<v.size()<<"\n"; for (auto u : v) cout<<u.first<<" "<<u.second<<"\n"; } int main() { int t; cin>>t; while (t--) solve(); }
#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...