Submission #238203

#	Time	Username	Problem	Language	Result	Execution time	Memory
238203		rama_pang	Sorting (IOI15_sorting)	C++14	74 / 100	1077 ms	114944 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.

class DisjointSet {
 private:
  int n, cc;
  vector<int> p;
  vector<int> sz;
  vector<array<int, 3>> history; // (id, p[id], sz[id])

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

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

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

  int CountComponent() {
    return cc;
  }

  int Size() {
    return n;
  }

  void Rollback(int x) {
    while (x--) {
      cc++;
      p[history.back()[0]] = history.back()[1];
      sz[history.back()[0]] = history.back()[2];
      history.pop_back();
      p[history.back()[0]] = history.back()[1];
      sz[history.back()[0]] = history.back()[2];
      history.pop_back();
    }
  }
};

const int MAXN = 600005;
DisjointSet D;
vector<array<int, 2>> tree[2 * MAXN];

void AddEdge(int a, int b, int t1, int t2, int n = 1, int l = 0, int r = MAXN - 1) {
  if (t2 < l || r < t1 || l > r || t1 > t2) return;
  if (t1 <= l && r <= t2) return void(tree[n].push_back({a, b}));
  int mid = (l + r) / 2;
  int z = n + 2 * (mid - l + 1);
  AddEdge(a, b, t1, t2, n + 1, l, mid);
  AddEdge(a, b, t1, t2, z, mid + 1, r);
}

void DfsSolve(int &res, int n = 1, int tl = 0, int tr = MAXN - 1) {
  int op = 0;
  for (auto &e : tree[n]) {
    op += D.Unite(e[0], e[1]);
  }
  if (tl == tr) {
    int swaps_needed = D.Size() - D.CountComponent();
    if (swaps_needed <= tl + 1) res = min(res, tl + 1);
  } else {
    int mid = (tl + tr) / 2;
    int z = n + 2 * (mid - tl + 1);
    DfsSolve(res, n + 1, tl, mid);
    DfsSolve(res, z, mid + 1, tr);
  }
  return D.Rollback(op);
}

int FindOptimalR(int N, vector<int> S, int M, vector<int> X, vector<int> Y) {
  vector<int> edge(N); // time
  for (int i = 0; i < N; i++) {
    edge[i] = 0;
  }
  
  for (int i = 0; i < M; i++) {
    AddEdge(X[i], S[X[i]], edge[X[i]], i - 1);
    AddEdge(Y[i], S[Y[i]], edge[Y[i]], i - 1);
    swap(S[X[i]], S[Y[i]]);
    edge[X[i]] = edge[Y[i]] = i;
  }
  for (int i = 0; i < N; i++) {
    AddEdge(i, S[i], edge[i], M - 1);
  }

  D = DisjointSet(N);
  int R = M;
  DfsSolve(R);
  return R;
}

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:19:22: warning: declaration of 'n' shadows a member of 'DisjointSet' [-Wshadow]
   DisjointSet(int n) : n(n), cc(n) {
                      ^
sorting.cpp:12:7: note: shadowed declaration is here
   int n, cc;
       ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:140: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: 0 / 26