Submission #529300

#	Time	Username	Problem	Language	Result	Execution time	Memory
529300		Cyanmond	Sorting (IOI15_sorting)	C++17	0 / 100	97 ms	388 KiB

sorting

// clang-format off
#include <bits/stdc++.h>

using i64 = int64_t;

namespace space {
template <typename T> bool setmax(T &v, const T a) {
    if (v < a) {
        v = a;
        return true;
    } else {
        return false;
    }
}

template <typename T> bool setmin(T &v, const T a) {
    if (v > a) {
        v = a;
        return true;
    } else {
        return false;
    }
}

int N, M;
std::vector<int> S, X, Y, P, Q;

std::vector<int> RS;

void swap(const int a, const int b) {
    P.push_back(a);
    Q.push_back(b);
    std::swap(S[a], S[b]);
}

int solve() {
    int best = M;
    for (int step = 0; step <= M; ++step) {
        std::vector<int> w(N);
        std::iota(w.begin(), w.end(), 0);
        for (int i = 0; i < step; ++i)
            std::swap(w[X[i]], w[Y[i]]);

        auto s = S;
        for (int i = 0; i < N; ++i) {
            s[w[i]] = S[i];
        }

        // sort s
        int sum = 0;
        for (int i = 0; i < N; ++i) {
            if (s[i] == i) continue;
            if (s[s[i]] == i and i < s[i]) continue;
            ++sum;
        }
        if (sum <= step) setmin(best, step);
    }

    const int step = best;
    std::vector<std::pair<int, int>> swaps;

    std::vector<int> w(N);
    std::iota(w.begin(), w.end(), 0);
    for (int i = 0; i < step; ++i)
        std::swap(w[X[i]], w[Y[i]]);

    auto s = S;
    for (int i = 0; i < N; ++i) {
        s[w[i]] = S[i];
    }

    std::vector<int> rs(N);
    for (int i = 0; i < N; ++i)
        rs[s[i]] = i;
    int sum = 0;
    for (int i = 0; i < N; ++i) {
        if (s[i] == i) continue;
        if (s[s[i]] == i and i < s[i]) continue;
        swaps.push_back({i, s[i]});
        ++sum;
    }

    for (int i = 0; i < (int)swaps.size(); ++i) {
        P.push_back(rs[swaps[i].first]);
        Q.push_back(rs[swaps[i].second]);
        std::swap(s[X[step - i - 1]], s[Y[step - i - 1]]);
        std::swap(rs[s[X[step - i - 1]]], rs[s[Y[step - i - 1]]]);
    }

    while ((int)P.size() < step) {
        P.push_back(0);
        Q.push_back(0);
    }
    std::reverse(P.begin(), P.end());
    std::reverse(Q.begin(), Q.end());
    return step;
}

int mfindSwapSpace(int n, int s[], int m, int x[], int y[], int rp[], int rq[]) {
    N = n;
    M = m;
    S.resize(N);
    X.resize(M);
    Y.resize(M);
    RS.resize(N);
    for (int i = 0; i < N; ++i) {
        S[i] = s[i];
        RS[S[i]] = i;
    }
    for (int i = 0; i < M; ++i) {
        X[i] = x[i];
        Y[i] = y[i];
    }
    int R = solve();

    for (int i = 0; i < R; ++i) {
        bool is_sorted = true;
        for (int j = 0; j < N; ++j)
            if (S[i] != j) is_sorted = false;
        if (is_sorted) {
            R = i;
            P.erase(P.begin() + i + 1, P.end());
            Q.erase(Q.begin() + i + 1, Q.end());
            break;
        }
        std::swap(S[X[i]], S[Y[i]]);
        std::swap(S[P[i]], S[Q[i]]);
    }

    for (int i = 0; i < R; ++i) {
        rp[i] = P[i];
        rq[i] = Q[i];
    }
    return R;
}
} // namespace space

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    return space::mfindSwapSpace(N, S, M, X, Y, P, Q);
}

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