oj.uz

Submission #315280

# Submission time Handle Problem Language Result Execution time Memory
315280 2020-10-22T08:18:56 Z casperwang Cat (info1cup19_cat) C++14
100 / 100
 546 ms 20200 KB 
#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[MAXN+1];
int cnt;
vector <pii> ans;

void swp(int x, int y) {
  swap(a[n-x+1], a[n-y+1]);
  swap(p[a[n-x+1]], p[a[n-y+1]]);
  swap(a[x], a[y]);
  swap(p[a[x]], p[a[y]]);
}

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

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;
      need[i] = 0;
      c[i] = tmp[i] = 0;
    }
    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]);
        swap(p[a[i]], p[a[n-i+1]]);
        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";
    }
  }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 640 KB Output is correct
2 Correct 21 ms 768 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 21 ms 640 KB Output is correct
3 Correct 21 ms 768 KB Output is correct
4 Correct 26 ms 640 KB Output is correct
5 Correct 10 ms 512 KB Output is correct
6 Correct 7 ms 512 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 640 KB Output is correct
2 Correct 21 ms 768 KB Output is correct
3 Correct 489 ms 16212 KB Output is correct
4 Correct 468 ms 16108 KB Output is correct
5 Correct 508 ms 20200 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 21 ms 640 KB Output is correct
3 Correct 21 ms 768 KB Output is correct
4 Correct 26 ms 640 KB Output is correct
5 Correct 10 ms 512 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 489 ms 16212 KB Output is correct
8 Correct 468 ms 16108 KB Output is correct
9 Correct 508 ms 20200 KB Output is correct
10 Correct 496 ms 12728 KB Output is correct
11 Correct 448 ms 11512 KB Output is correct
12 Correct 501 ms 18408 KB Output is correct
13 Correct 546 ms 19984 KB Output is correct
14 Correct 494 ms 18028 KB Output is correct