제출 #707804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
707804		baojiaopisu	정렬하기 (IOI15_sorting)	C++14	100 / 100	197 ms	28416 KiB

sorting

#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;
} 

컴파일 시 표준 에러 (stderr) 메시지

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 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26