oj.uz

Submission #639792

# Submission time Handle Problem Language Result Execution time Memory
639792 2022-09-11T17:14:12 Z Dec0Dedd Cat (info1cup19_cat) C++14
25 / 100
 925 ms 26664 KB 
#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();
}

Subtask #1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 956 KB Output is correct
2 Correct 41 ms 972 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 956 KB Output is correct
2 Correct 41 ms 972 KB Output is correct
3 Correct 925 ms 25344 KB Output is correct
4 Correct 870 ms 24748 KB Output is correct
5 Correct 883 ms 26664 KB Output is correct

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -