oj.uz

Submission #315178

# Submission time Handle Problem Language Result Execution time Memory
315178 2020-10-22T03:55:06 Z casperwang Cat (info1cup19_cat) C++14
36.25 / 100
 570 ms 19680 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 p[MAXN+1];
bool need[MAXN+1];
int tmp, cnt;
vector <pii> ans;

void output(int N) {
  cout << "\n";
  for (int i = 1; i <= N; i++)
    cout << a[i] << " \n"[i==N];
}
 
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 {
        need[i] ^= 1, need[p[i]] ^= 1;
        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, tmp));
        ans.pb(pii(i, n-tmp+1));
      }
      cnt++;
      tmp = 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;
    for (int i = 1; i <= n; i++)
      need[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]);
        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";
    }
  }
}

Subtask #1
2.25 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correctly distinguished between possibility and impossibility

Subtask #2
10.0 / 10.0

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

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correctly distinguished between possibility and impossibility
2 Correct 21 ms 640 KB Output is correct
3 Correct 24 ms 512 KB Output is correct
4 Correct 25 ms 760 KB Correctly distinguished between possibility and impossibility
5 Correct 9 ms 512 KB Correctly distinguished between possibility and impossibility
6 Correct 9 ms 512 KB Correctly distinguished between possibility and impossibility

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 640 KB Output is correct
2 Correct 24 ms 512 KB Output is correct
3 Correct 485 ms 14704 KB Output is correct
4 Correct 468 ms 14056 KB Output is correct
5 Correct 523 ms 17256 KB Output is correct

Subtask #5
5.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correctly distinguished between possibility and impossibility
2 Correct 21 ms 640 KB Output is correct
3 Correct 24 ms 512 KB Output is correct
4 Correct 25 ms 760 KB Correctly distinguished between possibility and impossibility
5 Correct 9 ms 512 KB Correctly distinguished between possibility and impossibility
6 Correct 9 ms 512 KB Correctly distinguished between possibility and impossibility
7 Correct 485 ms 14704 KB Output is correct
8 Correct 468 ms 14056 KB Output is correct
9 Correct 523 ms 17256 KB Output is correct
10 Correct 557 ms 14324 KB Correctly distinguished between possibility and impossibility
11 Correct 485 ms 12268 KB Correctly distinguished between possibility and impossibility
12 Correct 554 ms 17176 KB Correctly distinguished between possibility and impossibility
13 Correct 570 ms 19680 KB Correctly distinguished between possibility and impossibility
14 Correct 518 ms 17280 KB Correctly distinguished between possibility and impossibility