oj.uz

Submission #639814

# Submission time Handle Problem Language Result Execution time Memory
639814 2022-09-11T18:30:48 Z Dec0Dedd Cat (info1cup19_cat) C++14
61 / 100
 895 ms 13156 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]);
   }

   for (int i=1; i<n; ++i) assert(p[i] < p[i+1]);

   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 9 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Output is correct
2 Correct 41 ms 412 KB Output is correct
3 Correct 40 ms 496 KB Output is correct
4 Partially correct 43 ms 532 KB Valid reconstruction
5 Partially correct 18 ms 400 KB Valid reconstruction
6 Partially correct 14 ms 392 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 412 KB Output is correct
2 Correct 40 ms 496 KB Output is correct
3 Correct 885 ms 10440 KB Output is correct
4 Correct 835 ms 9920 KB Output is correct
5 Correct 877 ms 12352 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Output is correct
2 Correct 41 ms 412 KB Output is correct
3 Correct 40 ms 496 KB Output is correct
4 Partially correct 43 ms 532 KB Valid reconstruction
5 Partially correct 18 ms 400 KB Valid reconstruction
6 Partially correct 14 ms 392 KB Valid reconstruction
7 Correct 885 ms 10440 KB Output is correct
8 Correct 835 ms 9920 KB Output is correct
9 Correct 877 ms 12352 KB Output is correct
10 Partially correct 852 ms 10232 KB Valid reconstruction
11 Partially correct 821 ms 8648 KB Valid reconstruction
12 Partially correct 870 ms 11712 KB Valid reconstruction
13 Partially correct 895 ms 13156 KB Valid reconstruction
14 Partially correct 863 ms 11436 KB Valid reconstruction