oj.uz

Submission #315190

# Submission time Handle Problem Language Result Execution time Memory
315190 2020-10-22T04:19:04 Z casperwang Cat (info1cup19_cat) C++14
51.25 / 100
 594 ms 21196 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, 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.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 632 KB Output is correct
2 Correct 22 ms 640 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 632 KB Output is correct
3 Correct 22 ms 640 KB Output is correct
4 Partially correct 30 ms 744 KB Valid reconstruction
5 Partially correct 9 ms 512 KB Valid reconstruction
6 Partially correct 9 ms 512 KB Valid reconstruction

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 632 KB Output is correct
2 Correct 22 ms 640 KB Output is correct
3 Correct 551 ms 15596 KB Output is correct
4 Correct 484 ms 14952 KB Output is correct
5 Correct 533 ms 18724 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 632 KB Output is correct
3 Correct 22 ms 640 KB Output is correct
4 Partially correct 30 ms 744 KB Valid reconstruction
5 Partially correct 9 ms 512 KB Valid reconstruction
6 Partially correct 9 ms 512 KB Valid reconstruction
7 Correct 551 ms 15596 KB Output is correct
8 Correct 484 ms 14952 KB Output is correct
9 Correct 533 ms 18724 KB Output is correct
10 Partially correct 534 ms 14620 KB Valid reconstruction
11 Partially correct 482 ms 12812 KB Valid reconstruction
12 Partially correct 547 ms 18792 KB Valid reconstruction
13 Partially correct 594 ms 21196 KB Valid reconstruction
14 Partially correct 539 ms 18792 KB Valid reconstruction