oj.uz

Submission #707803

# Submission time Handle Problem Language Result Execution time Memory
707803 2023-03-10T07:31:07 Z baojiaopisu Sorting (IOI15_sorting) C++14
0 / 100
 2 ms 468 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
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 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
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 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -