oj.uz

Submission #391562

# Submission time Handle Problem Language Result Execution time Memory
391562 2021-04-19T10:55:33 Z usachevd0 Sorting (IOI15_sorting) C++14
100 / 100
 203 ms 20320 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }
void debug_out() { cerr << endl; }
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); }
template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; }
#ifdef DEBUG
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) { for (auto x : v) stream << x << ' '; return stream; }
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; }

int findSwapPairs(int n, int* s, int m, int* X, int* Y, int* ansX, int* ansY) {
  auto good = [&](int k, bool restore) {
    vector<int> p(s, s + n);
    for (int i = 0; i < k; ++i) {
      swap(p[X[i]], p[Y[i]]);
    }
    vector<char> used(n, false);
    int ptr = 0;
    vector<int> u(k), v(k);
    for (int x = 0; x < n; ++x) {
      if (!used[x]) {
        int y = x;
        do {
          used[y] = true;
          if (p[y] != x) {
            if (ptr == k) {
              return false;
            }
            u[ptr] = y;
            v[ptr] = p[y];
            ++ptr;
          }
          y = p[y];
        } while (y != x);
      }
    }
    if (restore) {
      vector<int> p(s, s + n);
      vector<int> ip(n);
      for (int x = 0; x < n; ++x) {
        ip[p[x]] = x;
      }
      for (int i = 0; i < k; ++i) {
        int a = p[X[i]];
        int b = p[Y[i]];
        swap(p[X[i]], p[Y[i]]);
        swap(ip[a], ip[b]);

        int k = ip[u[i]];
        int l = ip[v[i]];
        ansX[i] = k;
        ansY[i] = l;
        swap(p[k], p[l]);
        swap(ip[u[i]], ip[v[i]]);
      }
    }
    return true;
  };

  int vl = -1;
  int vr = m;
  while (vr - vl > 1) {
    int vm = (vl + vr) >> 1;
    if (good(vm, false)) {
      vr = vm;
    } else {
      vl = vm;
    }
  }
  good(vr, true);
  return vr;
}

#ifdef DEBUG
signed main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  int* s = new int[n];
  for (int x = 0; x < n; ++x) {
    cin >> s[x];
  }
  int m;
  cin >> m;
  int* x = new int[m];
  int* y = new int[m];
  for (int i = 0; i < m; ++i) {
    cin >> x[i] >> y[i];
  }
  int* p = new int[m];
  int* q = new int[m];
  int R = findSwapPairs(n, s, m, x, y, p, q);
  cout << R << '\n';
  for (int i = 0; i < R; ++i) {
    cout << p[i] << ' ' << q[i] << '\n';
  }
    
  return 0;
}
#endif

Compilation message

sorting.cpp: In lambda function:
sorting.cpp:59:21: warning: declaration of 'p' shadows a previous local [-Wshadow]
   59 |       vector<int> p(s, s + n);
      |                     ^
sorting.cpp:34:17: note: shadowed declaration is here
   34 |     vector<int> p(s, s + n);
      |                 ^
sorting.cpp:70:13: warning: declaration of 'int k' shadows a parameter [-Wshadow]
   70 |         int k = ip[u[i]];
      |             ^
sorting.cpp:33:23: note: shadowed declaration is here
   33 |   auto good = [&](int k, bool restore) {
      |                   ~~~~^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 292 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 2 ms 588 KB Output is correct
23 Correct 1 ms 588 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 1 ms 588 KB Output is correct
26 Correct 1 ms 552 KB Output is correct
27 Correct 1 ms 464 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 432 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 432 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 356 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 440 KB Output is correct
14 Correct 1 ms 332 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 432 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 432 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 356 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 440 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 165 ms 18316 KB Output is correct
16 Correct 170 ms 18660 KB Output is correct
17 Correct 199 ms 19532 KB Output is correct
18 Correct 64 ms 16452 KB Output is correct
19 Correct 138 ms 18044 KB Output is correct
20 Correct 150 ms 18628 KB Output is correct
21 Correct 146 ms 18752 KB Output is correct
22 Correct 184 ms 14876 KB Output is correct
23 Correct 181 ms 20320 KB Output is correct
24 Correct 194 ms 19864 KB Output is correct
25 Correct 186 ms 19732 KB Output is correct
26 Correct 144 ms 18624 KB Output is correct
27 Correct 126 ms 18064 KB Output is correct
28 Correct 198 ms 19988 KB Output is correct
29 Correct 181 ms 19176 KB Output is correct
30 Correct 96 ms 17648 KB Output is correct
31 Correct 184 ms 19740 KB Output is correct
32 Correct 184 ms 19440 KB Output is correct
33 Correct 188 ms 19984 KB Output is correct
34 Correct 184 ms 20068 KB Output is correct
35 Correct 144 ms 17860 KB Output is correct
36 Correct 57 ms 17652 KB Output is correct
37 Correct 203 ms 20256 KB Output is correct
38 Correct 187 ms 19600 KB Output is correct
39 Correct 192 ms 19504 KB Output is correct