제출 #368401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
368401		KoD	Sorting (IOI15_sorting)	C++17	100 / 100	531 ms	24544 KiB

sorting

#ifndef LOCAL
#include "sorting.h"
#endif

#include <vector>
#include <iostream>
#include <numeric>
#include <algorithm>
#include <queue>

template <class T>
using Vec = std::vector<T>;

struct DSU {
    Vec<int> par;
    DSU(const int n): par(n, -1) { }
    int find(const int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (par[x] > par[y]) {
            std::swap(x, y);
        }
        par[x] += par[y];
        par[y] = x;
        return true;
    }
};

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int ok = M, ng = -1;
    while (ok - ng > 1) {
        int md = (ok + ng) / 2;
        Vec<int> perm(N);
        Vec<int> inv(N);
        std::iota(perm.begin(), perm.end(), 0);
        std::iota(inv.begin(), inv.end(), 0);
        const auto swap = [&](const int i, const int j) {
            std::swap(perm[i], perm[j]);
            inv[perm[i]] = i;
            inv[perm[j]] = j;
        };
        for (int i = 0; i < md; ++i) {
            swap(X[i], Y[i]);
        }
        std::queue<std::pair<int, int>> que;
        {
            Vec<int> to(N);
            for (int i = 0; i < N; ++i) {
                to[S[i]] = inv[i];
            }
            Vec<char> used(N);
            for (int i = 0; i < N; ++i) {
                if (!used[i]) {
                    Vec<int> path;
                    {
                        int u = i;
                        while (!used[u]) {
                            path.push_back(u);
                            used[u] = true;
                            u = to[u];
                        }
                    }
                    for (int j = 0; j + 1 < (int) path.size(); ++j) {
                        que.emplace(path[0], path[j + 1]);
                    }
                }
            }
        }
        if ((int) que.size() > md) {
            ng = md;
            continue;
        }
        ok = md;
        for (int i = 0; i < N; ++i) {
            perm[i] = S[i];
            inv[S[i]] = i;
        }
        for (int i = 0; i < md; ++i) {
            swap(X[i], Y[i]);
            if (que.empty()) {
                P[i] = Q[i] = 0;
            }   
            else {
                const auto [x, y] = que.front();
                que.pop();
                const auto s = inv[x];
                const auto t = inv[y];
                P[i] = s;
                Q[i] = t;
                swap(s, t);
            }
        }
    }
    return ok;
}

#ifdef LOCAL
int main() {
    int N;
    std::cin >> N;
    int S[100] = {};
    for (int i = 0; i < N; ++i) {
        std::cin >> S[i];
    }
    int M;
    std::cin >> M;
    int X[100] = {};
    int Y[100] = {};
    for (int i = 0; i < M; ++i) {
        std::cin >> X[i] >> Y[i];
    }
    int P[100] = {};
    int Q[100] = {};
    int R = findSwapPairs(N, S, M, X, Y, P, Q);
    for (int i = 0; i < R; ++i) {
        std::swap(S[X[i]], S[Y[i]]);
        std::swap(S[P[i]], S[Q[i]]);
    }
    std::cout << R << '\n';
    for (int i = 0; i < N; ++i) {
        std::cout << S[i] << " \n"[i + 1 == N];
    }
    return 0;
}
#endif

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26