Submission #315190

#	Time	Username	Problem	Language	Result	Execution time	Memory
315190		casperwang	Cat (info1cup19_cat)	C++14	51.25 / 100	594 ms	21196 KiB

cat

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
 
const int MAXN = 3000000;
int t, n;
int a[MAXN+1];
int c[MAXN+1];
int p[MAXN+1];
bool need[MAXN+1];
int tmp, cnt;
vector <pii> ans;

void solve(int N) {
  for (int i = 1; i <= N; i++) {
    if (a[i] != i) {
      if (!need[i] && !need[p[i]]) {
        ans.pb(pii(i, p[i]));
        swap(a[n-i+1], a[n-p[i]+1]);
        swap(p[a[n-i+1]], p[a[n-p[i]+1]]);
        swap(a[i], a[p[i]]);
        swap(p[a[i]], p[a[p[i]]]);
      } else {
        if (need[i] && need[p[i]])
          need[i] = need[p[i]] = 0;
        ans.pb(pii(i, n-p[i]+1));
        swap(a[n-i+1], a[n-p[i]+1]);
        swap(p[a[n-i+1]], p[a[n-p[i]+1]]);
        swap(a[i], a[p[i]]);
        swap(p[a[i]], p[a[p[i]]]);
      }
    }
  }
  cnt = 0;
  for (int i = 1; i <= N; i++) {
    if (need[i]) {
      if (cnt % 2) {
        ans.pb(pii(i, n-tmp+1));
        ans.pb(pii(i, tmp));
      }
      cnt++;
      tmp = i;
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> t;
  while (t--) {
    cin >> n;
    bool tf = 1;
    for (int i = 1; i <= n; i++)
      cin >> a[i], p[a[i]] = i;
    for (int i = 1; i <= n; i++)
      need[i] = 0, c[i] = a[i];
    ans.clear();
    cnt = 0;
    for (int i = 1; i <= n/2 && tf; i++) {
      if (abs(a[n-i+1] + a[i]) != n+1) tf = 0;
      if (a[i] > n/2) {
        swap(a[n-i+1], a[i]);
        p[a[n-i+1]] = n-i+1;
        p[a[i]] = i;
        need[i] = 1;
        cnt++;
      }
    }
    if (cnt % 2) tf = 0;
    if (!tf) {
      cout << -1 << "\n";
    } else {
      solve(n/2);
      cout << ans.size() << " " << ans.size() << "\n";
      for (pii o : ans) {
        cout << o.ff << " " << o.ss << "\n";
        swap(c[o.ff], c[o.ss]);
        swap(c[n-o.ff+1], c[n-o.ss+1]);
      }
    }
  }
}

• Subtask 1: 5.25 / 15
• Subtask 2: 10 / 10
• Subtask 3: 8.75 / 25
• Subtask 4: 15 / 15
• Subtask 5: 12.25 / 35