oj.uz

Submission #639810

# Submission time Handle Problem Language Result Execution time Memory
639810 2022-09-11T18:25:30 Z Dec0Dedd Cat (info1cup19_cat) C++14
61 / 100
 954 ms 13216 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], n-k[i+1]+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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 492 KB Output is correct
2 Correct 41 ms 452 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 340 KB Output is correct
2 Correct 44 ms 492 KB Output is correct
3 Correct 41 ms 452 KB Output is correct
4 Partially correct 53 ms 508 KB Valid reconstruction
5 Partially correct 17 ms 412 KB Valid reconstruction
6 Partially correct 19 ms 392 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 492 KB Output is correct
2 Correct 41 ms 452 KB Output is correct
3 Correct 868 ms 10328 KB Output is correct
4 Correct 870 ms 9776 KB Output is correct
5 Correct 886 ms 12164 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 340 KB Output is correct
2 Correct 44 ms 492 KB Output is correct
3 Correct 41 ms 452 KB Output is correct
4 Partially correct 53 ms 508 KB Valid reconstruction
5 Partially correct 17 ms 412 KB Valid reconstruction
6 Partially correct 19 ms 392 KB Valid reconstruction
7 Correct 868 ms 10328 KB Output is correct
8 Correct 870 ms 9776 KB Output is correct
9 Correct 886 ms 12164 KB Output is correct
10 Partially correct 893 ms 10384 KB Valid reconstruction
11 Partially correct 854 ms 8624 KB Valid reconstruction
12 Partially correct 876 ms 11492 KB Valid reconstruction
13 Partially correct 954 ms 13216 KB Valid reconstruction
14 Partially correct 879 ms 11340 KB Valid reconstruction