oj.uz

Submission #315153

# Submission time Handle Problem Language Result Execution time Memory
315153 2020-10-22T03:29:29 Z casperwang Cat (info1cup19_cat) C++14
36.25 / 100
 561 ms 19504 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];
int tmp, cnt;
vector <pii> ans;

void solve(int N) {
  for (int i = 1; i <= N; i++) {
    if (a[i] != i) {
      ans.pb(pii(i, p[i]));
      swap(a[i], a[p[i]]);
      swap(p[a[i]], p[a[p[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;
    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;
        if (cnt % 2) ans.pb(pii(i, tmp));
        cnt++;
        tmp = n-i+1;
      }
    }
    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 4 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 628 KB Output is correct
2 Correct 20 ms 640 KB Output is correct

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Correctly distinguished between possibility and impossibility
2 Correct 21 ms 628 KB Output is correct
3 Correct 20 ms 640 KB Output is correct
4 Correct 24 ms 768 KB Correctly distinguished between possibility and impossibility
5 Correct 9 ms 512 KB Correctly distinguished between possibility and impossibility
6 Correct 7 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 628 KB Output is correct
2 Correct 20 ms 640 KB Output is correct
3 Correct 468 ms 14552 KB Output is correct
4 Correct 446 ms 13928 KB Output is correct
5 Correct 491 ms 17128 KB Output is correct

Subtask #5
5.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Correctly distinguished between possibility and impossibility
2 Correct 21 ms 628 KB Output is correct
3 Correct 20 ms 640 KB Output is correct
4 Correct 24 ms 768 KB Correctly distinguished between possibility and impossibility
5 Correct 9 ms 512 KB Correctly distinguished between possibility and impossibility
6 Correct 7 ms 512 KB Correctly distinguished between possibility and impossibility
7 Correct 468 ms 14552 KB Output is correct
8 Correct 446 ms 13928 KB Output is correct
9 Correct 491 ms 17128 KB Output is correct
10 Correct 498 ms 14324 KB Correctly distinguished between possibility and impossibility
11 Correct 455 ms 12272 KB Correctly distinguished between possibility and impossibility
12 Correct 492 ms 17000 KB Correctly distinguished between possibility and impossibility
13 Correct 561 ms 19504 KB Correctly distinguished between possibility and impossibility
14 Correct 511 ms 17256 KB Correctly distinguished between possibility and impossibility