oj.uz

Submission #639817

# Submission time Handle Problem Language Result Execution time Memory
639817 2022-09-11T18:51:23 Z Dec0Dedd Cat (info1cup19_cat) C++14
100 / 100
 916 ms 14900 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] == i) continue;
      int j=x[i];

      if (j <= n/2) swp(i, j);
      else {
         if (n-j+1 == i) k.push_back(i);
         else swp(i, j);
      }
   }

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 484 KB Output is correct
2 Correct 41 ms 488 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 42 ms 484 KB Output is correct
3 Correct 41 ms 488 KB Output is correct
4 Correct 44 ms 588 KB Output is correct
5 Correct 18 ms 340 KB Output is correct
6 Correct 14 ms 468 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 484 KB Output is correct
2 Correct 41 ms 488 KB Output is correct
3 Correct 913 ms 13244 KB Output is correct
4 Correct 916 ms 12124 KB Output is correct
5 Correct 911 ms 14900 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 42 ms 484 KB Output is correct
3 Correct 41 ms 488 KB Output is correct
4 Correct 44 ms 588 KB Output is correct
5 Correct 18 ms 340 KB Output is correct
6 Correct 14 ms 468 KB Output is correct
7 Correct 913 ms 13244 KB Output is correct
8 Correct 916 ms 12124 KB Output is correct
9 Correct 911 ms 14900 KB Output is correct
10 Correct 876 ms 11628 KB Output is correct
11 Correct 837 ms 9676 KB Output is correct
12 Correct 888 ms 12776 KB Output is correct
13 Correct 897 ms 14500 KB Output is correct
14 Correct 897 ms 12448 KB Output is correct