Submission #1248530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248530		kunzaZa183	Sorting (IOI15_sorting)	C++20	100 / 100	120 ms	11900 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
  int l = 0, r = N + 1;
  while (l < r) {
    int mid = (l + r) / 2;

    vector<int> cur(N);
    for (int i = 0; i < N; i++)
      cur[i] = S[i];

    for (int i = 0; i < mid; i++) {
      swap(cur[X[i]], cur[Y[i]]);
    }

    vector<bool> visited(N);
    vector<pair<int, int>> vpii;
    for (int i = 0; i < N; i++) {
      if (!visited[i]) {
        visited[i] = 1;
        int tmpi = i;
        while (visited[cur[tmpi]] == 0) {
          vpii.emplace_back(tmpi, cur[tmpi]);
          tmpi = cur[tmpi];
          visited[tmpi] = 1;
        }
      }
    }

    if (vpii.size() > mid) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }

  vector<int> cur(N);
  for (int i = 0; i < N; i++)
    cur[i] = S[i];

  for (int i = 0; i < l; i++) {
    swap(cur[X[i]], cur[Y[i]]);
  }

  vector<bool> visited(N);
  vector<pair<int, int>> vpii;
  for (int i = 0; i < N; i++) {
    if (!visited[i]) {
      visited[i] = 1;
      int tmpi = i;
      while (visited[cur[tmpi]] == 0) {
        vpii.emplace_back(tmpi, cur[tmpi]);
        tmpi = cur[tmpi];
        visited[tmpi] = 1;
      }
    }
  }

  while (vpii.size() < l) {
    vpii.push_back({0, 0});
  }

  for (int i = 0; i < N; i++)
    cur[i] = S[i];
  vector<int> pos(N);
  for (int i = 0; i < N; i++) {
    pos[cur[i]] = i;
  }
  reverse(vpii.begin(), vpii.end());
  for (int i = 0; i < l; i++) {
    swap(pos[cur[X[i]]], pos[cur[Y[i]]]);
    swap(cur[X[i]], cur[Y[i]]);

    auto [a, b] = vpii.back();
    vpii.pop_back();

    P[i] = pos[a], Q[i] = pos[b];
    swap(cur[pos[a]], cur[pos[b]]);
    swap(pos[a], pos[b]);
  }

  return l;
}

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