oj.uz

Submission #238204

# Submission time Handle Problem Language Result Execution time Memory
238204 2020-06-10T08:05:39 Z rama_pang Sorting (IOI15_sorting) C++14
100 / 100
 317 ms 21900 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 4 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 256 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 256 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 4 ms 256 KB Output is correct
20 Correct 5 ms 256 KB Output is correct
21 Correct 6 ms 512 KB Output is correct
22 Correct 5 ms 512 KB Output is correct
23 Correct 5 ms 512 KB Output is correct
24 Correct 6 ms 512 KB Output is correct
25 Correct 5 ms 512 KB Output is correct
26 Correct 7 ms 512 KB Output is correct
27 Correct 6 ms 512 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 5 ms 512 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 245 ms 11488 KB Output is correct
16 Correct 257 ms 19680 KB Output is correct
17 Correct 278 ms 20676 KB Output is correct
18 Correct 48 ms 13432 KB Output is correct
19 Correct 202 ms 21316 KB Output is correct
20 Correct 228 ms 21900 KB Output is correct
21 Correct 208 ms 21764 KB Output is correct
22 Correct 246 ms 16096 KB Output is correct
23 Correct 286 ms 21596 KB Output is correct
24 Correct 277 ms 21144 KB Output is correct
25 Correct 317 ms 20860 KB Output is correct
26 Correct 208 ms 21796 KB Output is correct
27 Correct 179 ms 21268 KB Output is correct
28 Correct 270 ms 21208 KB Output is correct
29 Correct 267 ms 21132 KB Output is correct
30 Correct 146 ms 21492 KB Output is correct
31 Correct 273 ms 21532 KB Output is correct
32 Correct 261 ms 20680 KB Output is correct
33 Correct 286 ms 21100 KB Output is correct
34 Correct 273 ms 21036 KB Output is correct
35 Correct 220 ms 20948 KB Output is correct
36 Correct 83 ms 21396 KB Output is correct
37 Correct 296 ms 21876 KB Output is correct
38 Correct 273 ms 20964 KB Output is correct
39 Correct 280 ms 21080 KB Output is correct