Submission #368402

#	Time	Username	Problem	Language	Result	Execution time	Memory
368402		KoD	정렬하기 (IOI15_sorting)	C++17	100 / 100	725 ms	15724 KiB

sorting

#include <bits/stdc++.h>
#include "sorting.h"

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

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

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