Submission #238204

#	Time	Username	Problem	Language	Result	Execution time	Memory
238204		rama_pang	Sorting (IOI15_sorting)	C++14	100 / 100	317 ms	21900 KiB

sorting

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

// Solution:
// Add edge i -> S[i]. Minimum number of swaps needed is N - count_cycles(S)
// Cycles always form, we can simply maintain number of connected components with
// dynamic connectivity. We can recover answer easily. However this is not fast
// enough to fit in the time limit, as this approach is O(M log M log N).
//
// To optimize, observe that number of cycles after each swap only change by 1.
// For -1 swap pairs, we can use our turn to swap the same pair. Thus we can
// binary search the answer. This yields O(N log M).

class DisjointSet {
 private:
  int n, cc;
  vector<int> p;
  vector<int> sz;

 public:
  DisjointSet() {}
  DisjointSet(int n) : n(n), cc(n) {
    p.resize(n);
    iota(begin(p), end(p), 0);
    sz.assign(n, 1);
  }

  int Find(int x) {
    return p[x] == x ? x : p[x] = Find(p[x]);
  }

  int Unite(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return 0;
    cc--;
    if (sz[x] < sz[y]) {
      swap(x, y);
    }
    sz[x] += sz[y];
    p[y] = x;
    return 1;
  }

  int CountComponent() {
    return cc;
  }
};

int FindOptimalR(int N, vector<int> S, int M, vector<int> X, vector<int> Y) {
  auto Check = [&](int R) {
    DisjointSet D(N);
    for (int i = 0; i < R; i++) {
      swap(S[X[i]], S[Y[i]]);
    }
    for (int i = 0; i < N; i++) {
      D.Unite(i, S[i]);
    }
    int swaps_needed = N - D.CountComponent();
    for (int i = R - 1; i >= 0; i--) {
      swap(S[X[i]], S[Y[i]]);
    }
    return swaps_needed <= R;
  };
  
  int lo = 1, hi = M;
  while (lo < hi) {
    int md = (lo + hi) / 2;
    if (Check(md)) {
      hi = md;
    } else {
      lo = md + 1;
    }
  }
  return lo;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
  if (is_sorted(S, S + N)) return 0;
  int R = FindOptimalR(N, vector<int>(S, S + N), M, vector<int>(X, X + M), vector<int>(Y, Y + M));

  vector<int> pos(N), seq(N);
  for (int i = 0; i < N; i++) {
    pos[S[i]] = i;
    seq[i] = S[i];
  }

  vector<array<int, 2>> operations;
  for (int i = 0; i < R; i++) {
    swap(S[X[i]], S[Y[i]]);
  }
  for (int i = 0; i < N; i++) {
    while (i != S[i]) {
      operations.push_back({S[i], S[S[i]]});
      swap(S[i], S[S[i]]);
    }
  }
  while (operations.size() < R) {
    operations.push_back({0, 0});
  }

  for (int i = 0; i < R; i++) {
    swap(seq[X[i]], seq[Y[i]]);
    pos[seq[X[i]]] = X[i];
    pos[seq[Y[i]]] = Y[i];
    P[i] = pos[operations[i][0]];
    Q[i] = pos[operations[i][1]];
    swap(seq[P[i]], seq[Q[i]]);
    pos[seq[P[i]]] = P[i];
    pos[seq[Q[i]]] = Q[i];
  }

  return R;
}

Compilation message (stderr)

sorting.cpp: In constructor 'DisjointSet::DisjointSet(int)':
sorting.cpp:23:22: warning: declaration of 'n' shadows a member of 'DisjointSet' [-Wshadow]
   DisjointSet(int n) : n(n), cc(n) {
                      ^
sorting.cpp:17:7: note: shadowed declaration is here
   int n, cc;
       ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:98:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (operations.size() < R) {
          ~~~~~~~~~~~~~~~~~~^~~

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