oj.uz

Submission #639809

# Submission time Handle Problem Language Result Execution time Memory
639809 2022-09-11T18:23:56 Z Dec0Dedd Cat (info1cup19_cat) C++14
25 / 100
 907 ms 262144 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;
   }

   vector<int> k;
   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 if (p[r] > n/2 && p[r] != x[r] && x[r] != n-p[r]+1) swp(p[r], x[r]);
   }

   for (int i=1; i<=n/2; ++i) {
      if (p[i] > n/2) k.push_back(i);
   }

   assert(k.size()%2 == 0);
   for (int i=0; i<(int)k.size(); i+=2) swp(k[i], k[i+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) {
      assert(u.first != u.second);
      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 456 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 468 KB Output is correct
2 Correct 41 ms 468 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 456 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 468 KB Output is correct
2 Correct 41 ms 468 KB Output is correct
3 Correct 907 ms 10592 KB Output is correct
4 Correct 848 ms 9808 KB Output is correct
5 Correct 890 ms 12156 KB Output is correct

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 456 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -