oj.uz

Submission #315274

# Submission time Handle Problem Language Result Execution time Memory
315274 2020-10-22T08:01:17 Z casperwang Cat (info1cup19_cat) C++14
36.25 / 100
 599 ms 24168 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) {
      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] = 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";
    }
  }
}

Compilation message

cat.cpp: In function 'int main()':
cat.cpp:80:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   80 |       need[i] = c[i] = tmp[i] = 0;
      |                 ~~~~~^~~~~~~~~~~~

Subtask #1
2.25 / 15.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Correctly distinguished between possibility and impossibility
2 Correct 22 ms 768 KB Output is correct
3 Correct 22 ms 768 KB Output is correct
4 Correct 26 ms 888 KB Correctly distinguished between possibility and impossibility
5 Correct 10 ms 640 KB Correctly distinguished between possibility and impossibility
6 Correct 8 ms 640 KB Correctly distinguished between possibility and impossibility

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 768 KB Output is correct
2 Correct 22 ms 768 KB Output is correct
3 Correct 508 ms 17004 KB Output is correct
4 Correct 490 ms 17000 KB Output is correct
5 Correct 575 ms 21336 KB Output is correct

Subtask #5
5.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Correctly distinguished between possibility and impossibility
2 Correct 22 ms 768 KB Output is correct
3 Correct 22 ms 768 KB Output is correct
4 Correct 26 ms 888 KB Correctly distinguished between possibility and impossibility
5 Correct 10 ms 640 KB Correctly distinguished between possibility and impossibility
6 Correct 8 ms 640 KB Correctly distinguished between possibility and impossibility
7 Correct 508 ms 17004 KB Output is correct
8 Correct 490 ms 17000 KB Output is correct
9 Correct 575 ms 21336 KB Output is correct
10 Correct 558 ms 15476 KB Correctly distinguished between possibility and impossibility
11 Correct 502 ms 13932 KB Correctly distinguished between possibility and impossibility
12 Correct 557 ms 21992 KB Correctly distinguished between possibility and impossibility
13 Correct 599 ms 24168 KB Correctly distinguished between possibility and impossibility
14 Correct 579 ms 21860 KB Correctly distinguished between possibility and impossibility