oj.uz

Submission #639798

# Submission time Handle Problem Language Result Execution time Memory
639798 2022-09-11T17:51:18 Z Dec0Dedd Cat (info1cup19_cat) C++14
61 / 100
 909 ms 27652 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]) 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 42 ms 420 KB Output is correct
2 Correct 39 ms 508 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 42 ms 420 KB Output is correct
3 Correct 39 ms 508 KB Output is correct
4 Partially correct 45 ms 984 KB Valid reconstruction
5 Partially correct 21 ms 580 KB Valid reconstruction
6 Partially correct 14 ms 520 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 420 KB Output is correct
2 Correct 39 ms 508 KB Output is correct
3 Correct 875 ms 10276 KB Output is correct
4 Correct 896 ms 9772 KB Output is correct
5 Correct 866 ms 12204 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 42 ms 420 KB Output is correct
3 Correct 39 ms 508 KB Output is correct
4 Partially correct 45 ms 984 KB Valid reconstruction
5 Partially correct 21 ms 580 KB Valid reconstruction
6 Partially correct 14 ms 520 KB Valid reconstruction
7 Correct 875 ms 10276 KB Output is correct
8 Correct 896 ms 9772 KB Output is correct
9 Correct 866 ms 12204 KB Output is correct
10 Partially correct 895 ms 23848 KB Valid reconstruction
11 Partially correct 829 ms 22412 KB Valid reconstruction
12 Partially correct 876 ms 26964 KB Valid reconstruction
13 Partially correct 909 ms 27652 KB Valid reconstruction
14 Partially correct 897 ms 26436 KB Valid reconstruction