oj.uz

Submission #707794

# Submission time Handle Problem Language Result Execution time Memory
707794 2023-03-10T07:05:26 Z baojiaopisu Sorting (IOI15_sorting) C++14
74 / 100
 1000 ms 23084 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];

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;
        // cout << a[i] << " ";
    }
    // cout << endl;

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

    for(int i = 0; i < m; i++) {
        P[i] = P[i + 1];
        Q[i] = Q[i + 1];
    }

    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:140:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  140 |     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:141:13: warning: declaration of 'y' shadows a global declaration [-Wshadow]
  141 |         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:150:13: warning: declaration of 'r' shadows a previous local [-Wshadow]
  150 |         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;
      |                ^
sorting.cpp:151:17: warning: declaration of 'i' shadows a previous local [-Wshadow]
  151 |         for(int i = 1; i <= n; i++) c[i] = i;
      |                 ^
sorting.cpp:148:13: note: shadowed declaration is here
  148 |     for(int i = ans; i >= 1; i--) {
      |             ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 324 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 448 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 324 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 448 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 412 KB Output is correct
21 Correct 2 ms 708 KB Output is correct
22 Correct 2 ms 724 KB Output is correct
23 Correct 2 ms 832 KB Output is correct
24 Correct 2 ms 724 KB Output is correct
25 Correct 1 ms 816 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 2 ms 724 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 596 KB Output is correct
2 Correct 9 ms 580 KB Output is correct
3 Correct 7 ms 600 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 8 ms 648 KB Output is correct
9 Correct 9 ms 616 KB Output is correct
10 Correct 10 ms 640 KB Output is correct
11 Correct 8 ms 596 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 9 ms 620 KB Output is correct
14 Correct 1 ms 596 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 596 KB Output is correct
2 Correct 9 ms 580 KB Output is correct
3 Correct 7 ms 600 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 8 ms 648 KB Output is correct
9 Correct 9 ms 616 KB Output is correct
10 Correct 10 ms 640 KB Output is correct
11 Correct 8 ms 596 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 9 ms 620 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Execution timed out 1041 ms 23084 KB Time limit exceeded
16 Halted 0 ms 0 KB -