oj.uz

Submission #639799

# Submission time Handle Problem Language Result Execution time Memory
639799 2022-09-11T17:54:00 Z Dec0Dedd Cat (info1cup19_cat) C++14
61 / 100
 908 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;
   }

   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 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) 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
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 45 ms 400 KB Output is correct
2 Correct 43 ms 484 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 45 ms 400 KB Output is correct
3 Correct 43 ms 484 KB Output is correct
4 Partially correct 44 ms 484 KB Valid reconstruction
5 Partially correct 16 ms 340 KB Valid reconstruction
6 Partially correct 15 ms 376 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 400 KB Output is correct
2 Correct 43 ms 484 KB Output is correct
3 Correct 874 ms 10304 KB Output is correct
4 Correct 840 ms 9912 KB Output is correct
5 Correct 863 ms 12268 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 45 ms 400 KB Output is correct
3 Correct 43 ms 484 KB Output is correct
4 Partially correct 44 ms 484 KB Valid reconstruction
5 Partially correct 16 ms 340 KB Valid reconstruction
6 Partially correct 15 ms 376 KB Valid reconstruction
7 Correct 874 ms 10304 KB Output is correct
8 Correct 840 ms 9912 KB Output is correct
9 Correct 863 ms 12268 KB Output is correct
10 Partially correct 854 ms 10304 KB Valid reconstruction
11 Partially correct 822 ms 8972 KB Valid reconstruction
12 Partially correct 860 ms 11584 KB Valid reconstruction
13 Partially correct 894 ms 13216 KB Valid reconstruction
14 Partially correct 908 ms 11324 KB Valid reconstruction