Submission #522296

#TimeUsernameProblemLanguageResultExecution timeMemory
522296amunduzbaevCat (info1cup19_cat)C++17
25 / 100
429 ms14076 KiB
#include "bits/stdc++.h" using namespace std; #define ar array typedef long long ll; void solve(){ int n; cin>>n; vector<int> a(n), pos(n); for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) pos[--a[i]] = i; vector<ar<int, 2>> res; auto add = [&](int i, int j){ int i_ = n - i - 1, j_ = n - j - 1; assert(j != i_); swap(a[i], a[j]); swap(pos[a[i]], pos[a[j]]); res.push_back({i, j}); swap(a[i_], a[j_]); swap(pos[a[i_]], pos[a[j_]]); }; vector<int> tmp; for(int i=0;i<n/2;i++){ if(a[i] == i){ if(a[n - i - 1] != n - i - 1) { cout<<-1<<"\n"; return; } continue; } int j = pos[i]; if(j < n/2){ add(i, j); } else { if(n - j - 1 < i){ cout<<-1<<"\n"; return; } if(n - j - 1 == i){ tmp.push_back(i); continue; } else { add(i, j); } } if(a[n - i - 1] != n - i - 1) { cout<<-1<<"\n"; return; } } if((int)tmp.size() & 1){ cout<<-1<<"\n"; return; } for(int i=0;i<(int)tmp.size();i+=2){ add(tmp[i], tmp[i+1]); add(tmp[i], pos[tmp[i]]); } cout<<(int)res.size()<<" "<<(int)res.size()<<"\n"; for(auto x : res) cout<<x[0] + 1<<" "<<x[1] + 1<<"\n"; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int t; cin>>t; while(t--){ solve(); } } /* 10 4 9 6 3 1 ' 10 8 5 2 7 1 9 6 3 4 ' 7 8 5 2 10 1 2 3 4 5 ' 6 7 8 9 10 6 2 6 4 ' 3 1 5 1 2 3 ' 4 5 6 */
#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...