Submission #529271

#	Time	Username	Problem	Language	Result	Execution time	Memory
529271		Cyanmond	Sorting (IOI15_sorting)	C++17	54 / 100	616 ms	588 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;
    }
}

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() {
    for (int step = 0; step < N; ++step) {
        bool is_sorted = true;
        for (int i = 0; i < N; ++i)
            if (S[i] != i) is_sorted = false;
        if (is_sorted) break;

        std::swap(S[X[step]], S[Y[step]]);

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

        auto idrev = [](std::vector<int> &vec) {
            std::vector<int> vec2(vec.size());
            for (int i = 0; i < (int)vec.size(); ++i)
                vec2[vec[i]] = i;
            vec = std::move(vec2);
        };

        idrev(w);

        const int pos_s = (int)(std::find(S.begin(), S.end(), step) - S.begin());
        if (w[pos_s] == step) {
            swap(0, 0);
            continue;
        }
        for (int i = 0; i < N; ++i) {
            if (i == step) continue;
            const int pos_i = (int)(std::find(S.begin(), S.end(), i) - S.begin());
            if (w[pos_i] == step) {
                swap(pos_s, pos_i);
                break;
            }
        }
    }
    return (int)P.size();
}

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];
    }
    const int R = solve();
    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: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26