oj.uz

Submission #315279

# Submission time Handle Problem Language Result Execution time Memory
315279 2020-10-22T08:13:08 Z casperwang Cat (info1cup19_cat) C++14
51.25 / 100
 602 ms 23656 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 dsu[MAXN+1];
int cnt;
vector <pii> ans;

int fnd(int a) {
  return a == dsu[a] ? a : dsu[a] = fnd(dsu[a]);
}

void Union(int a, int b) {
  a = fnd(a), b = fnd(b);
  dsu[min(a, b)] = max(a, b);
}

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]) {
      if (c[fnd(i)] % 2) {
        int temp = tmp[fnd(i)];
        ans.pb(pii(i, n-temp+1));
        swp(i, temp);
        need[i] = need[temp] = 0;
      }
      c[fnd(i)]++;
      tmp[fnd(i)] = i;
    }
  }
  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]));
        swp(i, tmp[0]);
        ans.pb(pii(i, n-tmp[0]+1));
        swp(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++;
      }
    }
    for (int i = 1; i <= n/2; i++)
      dsu[i] = i;
    for (int i = 1; i <= n/2; i++)
      Union(i, p[i]);
    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
5.25 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 384 KB Valid reconstruction

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 636 KB Output is correct
2 Correct 22 ms 632 KB Output is correct

Subtask #3
8.75 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 384 KB Valid reconstruction
2 Correct 22 ms 636 KB Output is correct
3 Correct 22 ms 632 KB Output is correct
4 Partially correct 26 ms 1024 KB Valid reconstruction
5 Partially correct 10 ms 512 KB Valid reconstruction
6 Partially correct 8 ms 512 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 636 KB Output is correct
2 Correct 22 ms 632 KB Output is correct
3 Correct 522 ms 16624 KB Output is correct
4 Correct 497 ms 16488 KB Output is correct
5 Correct 535 ms 20828 KB Output is correct

Subtask #5
12.25 / 35.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 384 KB Valid reconstruction
2 Correct 22 ms 636 KB Output is correct
3 Correct 22 ms 632 KB Output is correct
4 Partially correct 26 ms 1024 KB Valid reconstruction
5 Partially correct 10 ms 512 KB Valid reconstruction
6 Partially correct 8 ms 512 KB Valid reconstruction
7 Correct 522 ms 16624 KB Output is correct
8 Correct 497 ms 16488 KB Output is correct
9 Correct 535 ms 20828 KB Output is correct
10 Partially correct 557 ms 14964 KB Valid reconstruction
11 Partially correct 507 ms 13552 KB Valid reconstruction
12 Partially correct 559 ms 21740 KB Valid reconstruction
13 Partially correct 602 ms 23656 KB Valid reconstruction
14 Partially correct 563 ms 21476 KB Valid reconstruction