Submission #1187595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187595		JelalTkm	Sorting (IOI15_sorting)	C++20	100 / 100	96 ms	10972 KiB

sorting

#include <bits/stdc++.h>
#include "sorting.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

// #define int long long int

const int N = 2e5 + 10;
const int md = 1e9 + 7;
const int INF = 1e9;

int f(int ch, int n, int s[], int p[], int q[], int x[], int y[]) {
  vector<int> e(n), pos(n);
  for (int i = 0; i < n; i++) {
    e[i] = s[i];
    pos[e[i]] = i;
  }

  for (int i = 0; i < ch; i++) {
    swap(pos[e[x[i]]], pos[e[y[i]]]);
    swap(e[x[i]], e[y[i]]);
  }

  int cnt = 0;
  for (int i = 0; i < n; i++) {
    if (pos[i] == i) continue;
    p[cnt] = i, q[cnt] = e[i];
    swap(pos[i], pos[e[i]]);
    swap(e[i], e[pos[e[i]]]);
    cnt++;
  }

  return cnt;
}

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
  int l = -1, r = m + 1;
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    if (f(mid, n, s, p, q, x, y) <= mid) r = mid;
    else l = mid;
  }

  // for (int i = 0; i < m; i++)
  //   p[i] = 0, q[i] = 0;
  vector<int> pos(n);
  for (int i = 0; i < n; i++)
    pos[s[i]] = i;
  
  int co = f(r, n, s, p, q, x, y);

  for (int i = 0; i < co; i++) {
    swap(pos[s[x[i]]], pos[s[y[i]]]);
    swap(s[x[i]], s[y[i]]);
    int pp = pos[p[i]], qq = pos[q[i]];
    swap(pos[p[i]], pos[q[i]]);
    swap(s[pp], s[qq]);
    p[i] = pp, q[i] = qq;
  }
  for (int i = co; i < r; i++)
    p[i] = q[i] = 0;

  return r;
}

// int32_t main(int32_t argc, char *argv[]) {
//   ios::sync_with_stdio(false);
//   cin.tie(nullptr);
 
//   int T = 1;
//   // cin >> T;
//   while (T--) {
//     int n;
//     cin >> n;
//     int S[n];
//     for (int i = 0; i < n; i++)
//       cin >> S[i];
//     int m;
//     cin >> m;
//     int x[m], y[m];
//     for (int i = 0; i < m; i++)
//       cin >> x[i] >> y[i];

//     int p[m + 10], q[m + 10];
//     cout << findSwapPairs(n, S, m, x, y, p, q) << '\n';
//     for (int i = 0; i < 3; i++)
//       cout << p[i] << " " << q[i] << '\n';
//   }
 
//   return 0;
// }

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26