Submission #639817

#	Time	Username	Problem	Language	Result	Execution time	Memory
639817		Dec0Dedd	Cat (info1cup19_cat)	C++14	100 / 100	916 ms	14900 KiB

cat

#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 / 15
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15
• Subtask 5: 35 / 35