oj.uz

Submission #707804

# Submission time Handle Problem Language Result Execution time Memory
707804 2023-03-10T07:32:14 Z baojiaopisu Sorting (IOI15_sorting) C++14
100 / 100
 197 ms 28416 KB 
#include "sorting.h"
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;

#define fi first
#define se second
#define left BAO
#define right ANH
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz

#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

const int MOD = 1e9 + 7; //998244353

template<class X, class Y>
	void add(X &x, const Y &y) {
		x = (x + y);
		if(x >= MOD) x -= MOD;
	}

template<class X, class Y> 
	void sub(X &x, const Y &y) {
		x = (x - y);
		if(x < 0) x += MOD;
	}

/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/

const ll INF = 1e9;
const int N = 2e6 + 10;

int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N];
int par[N], pos[N], c[N], p[N];

int find_par(int u) {
    if(par[u] < 0) return u;
    par[u] = find_par(par[u]);
    return par[u];
}
bool merge(int u, int v) {
    u = find_par(u), v = find_par(v);
    if(u == v) return false;
    if(par[u] > par[v]) swap(u, v);
    par[u] += par[v];
    par[v] = u;
    return true;
}

int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
    for(int i = 1; i <= n; i++) {
        s[i] = S[i - 1] + 1;
    }

    for(int i = 1; i <= m; i++) {
        x[i] = X[i - 1] + 1;
        y[i] = Y[i - 1] + 1;
    }

    int l = 0, r = m, ans = 0;
    while(l <= r) {
        int mid = (l + r) >> 1;
        for(int i = 1; i <= n; i++) a[i] = s[i];
        for(int i = 1; i <= mid; i++) {
            swap(a[x[i]], a[y[i]]);
        }

        for(int i = 1; i <= n; i++) par[i] = -1;
        for(int i = 1; i <= n; i++) merge(i, a[i]);
        int cnt = 0;
        for(int i = 1; i <= n; i++) {
            if(find_par(i) == i) ++cnt;
        }

        if((n - cnt) <= mid) {
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }

    for(int i = 1; i <= n; i++) a[i] = s[i];
    for(int i = 1; i <= ans; i++) {
        swap(a[x[i]], a[y[i]]);
    }

    for(int i = 1; i <= n; i++) par[i] = -1;
    for(int i = 1; i <= n; i++) merge(i, a[i]);
    vector<int> q;
    for(int i = 1; i <= n; i++) {
        if(find_par(i) != i) q.pb(i);
    }

    for(int i = 1; i <= n; i++) {
        pos[a[i]] = i;
    }

    vector<pii> op;
    for(auto x : q) {
        int y = a[x];
        op.pb(mp(pos[x], x));
        swap(a[x], a[pos[x]]);
        pos[y] = pos[x];
        pos[x] = x;
    }

    for(int i = 1; i <= n; i++) c[i] = p[i] = i;
    for(int i = ans; i >= 1; i--) {
        if(op.empty()) break;
        int r = op.back().fi, t = op.back().se;
        r = c[r], t = c[t];
        P[i - 1] = r - 1;
        Q[i - 1] = t - 1;
        // swap(c[p[r]], c[p[t]]);
        // swap(p[r], p[t]);
        swap(c[p[x[i]]], c[p[y[i]]]);      
        swap(p[x[i]], p[y[i]]);
        op.pop_back(); 
    }

    return ans;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:90:73: warning: declaration of 'Q' shadows a global declaration [-Wshadow]
   90 | int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
      |                                                                     ~~~~^~~
sorting.cpp:73:11: note: shadowed declaration is here
   73 | int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N];
      |           ^
sorting.cpp:90:64: warning: declaration of 'P' shadows a global declaration [-Wshadow]
   90 | int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
      |                                                            ~~~~^~~
sorting.cpp:73:5: note: shadowed declaration is here
   73 | int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N];
      |     ^
sorting.cpp:90:55: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
   90 | int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
      |                                                   ~~~~^~~
sorting.cpp:73:35: note: shadowed declaration is here
   73 | int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N];
      |                                   ^
sorting.cpp:90:46: warning: declaration of 'X' shadows a global declaration [-Wshadow]
   90 | int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
      |                                          ~~~~^~~
sorting.cpp:73:29: note: shadowed declaration is here
   73 | int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N];
      |                             ^
sorting.cpp:90:30: warning: declaration of 'S' shadows a global declaration [-Wshadow]
   90 | int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
      |                          ~~~~^~~
sorting.cpp:73:47: note: shadowed declaration is here
   73 | int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N];
      |                                               ^
sorting.cpp:138:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  138 |     for(auto x : q) {
      |              ^
sorting.cpp:73:17: note: shadowed declaration is here
   73 | int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N];
      |                 ^
sorting.cpp:139:13: warning: declaration of 'y' shadows a global declaration [-Wshadow]
  139 |         int y = a[x];
      |             ^
sorting.cpp:73:23: note: shadowed declaration is here
   73 | int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N];
      |                       ^
sorting.cpp:149:13: warning: declaration of 'r' shadows a previous local [-Wshadow]
  149 |         int r = op.back().fi, t = op.back().se;
      |             ^
sorting.cpp:100:16: note: shadowed declaration is here
  100 |     int l = 0, r = m, ans = 0;
      |                ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 150 ms 17300 KB Output is correct
16 Correct 164 ms 25564 KB Output is correct
17 Correct 179 ms 26992 KB Output is correct
18 Correct 70 ms 22048 KB Output is correct
19 Correct 148 ms 25492 KB Output is correct
20 Correct 158 ms 26236 KB Output is correct
21 Correct 161 ms 26248 KB Output is correct
22 Correct 148 ms 22352 KB Output is correct
23 Correct 160 ms 28032 KB Output is correct
24 Correct 183 ms 27592 KB Output is correct
25 Correct 175 ms 27228 KB Output is correct
26 Correct 163 ms 26284 KB Output is correct
27 Correct 146 ms 25412 KB Output is correct
28 Correct 185 ms 27352 KB Output is correct
29 Correct 180 ms 26684 KB Output is correct
30 Correct 105 ms 24772 KB Output is correct
31 Correct 178 ms 27268 KB Output is correct
32 Correct 169 ms 26904 KB Output is correct
33 Correct 197 ms 27432 KB Output is correct
34 Correct 166 ms 27348 KB Output is correct
35 Correct 158 ms 25152 KB Output is correct
36 Correct 58 ms 23708 KB Output is correct
37 Correct 182 ms 28416 KB Output is correct
38 Correct 185 ms 27148 KB Output is correct
39 Correct 182 ms 27468 KB Output is correct