oj.uz

답안 #639814

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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