답안 #831084

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831084	2023-08-19T17:11:00 Z	skittles1412	정렬하기 (IOI15_sorting)	C++17	16 / 100	2 ms	596 KB

sorting

#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

template <typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}

vector<pair<int, int>> min_sort(vector<int> arr) {
    int n = sz(arr);

    vector<pair<int, int>> ans;

    for (int i = 0; i < n; i++) {
        if (arr[i] == i) {
            continue;
        }
        int u = int(find(begin(arr), end(arr), i) - arr.begin());
        ans.emplace_back(i, u);
        swap(arr[i], arr[u]);
    }

    return ans;
}

vector<pair<int, int>> solve(vector<int> arr,
                             const vector<pair<int, int>>& swaps) {
    int n = sz(arr);

    vector<int> res(n), pos(n);

    for (int i = 0; i < n; i++) {
        pos[arr[i]] = i;
    }

    {
        auto tmp = arr;
        for (auto& [u, v] : swaps) {
            swap(tmp[u], tmp[v]);
        }
        for (int i = 0; i < n; i++) {
            res[tmp[i]] = i;
        }
    }

    auto ans_swaps = min_sort(res);
    dbg(ans_swaps);
    assert(sz(ans_swaps) < sz(swaps));
    vector<pair<int, int>> ans;

    auto do_swap = [&](int u, int v, bool swap_res) -> void {
        swap(arr[u], arr[v]);
        swap(pos[arr[u]], pos[arr[v]]);
        if (swap_res) {
            swap(res[arr[u]], res[arr[v]]);
        }
    };

    for (int t = 0; t < sz(ans_swaps); t++) {
        {
            auto& [u, v] = swaps[t];
            do_swap(u, v, false);
        }
        {
            auto& [u, v] = ans_swaps[t];
            ans.emplace_back(pos[u], pos[v]);
            do_swap(pos[u], pos[v], true);
        }
    }
    for (int t = sz(ans_swaps); t < sz(swaps); t++) {
        ans.emplace_back(0, 0);
    }

    return ans;
}

void grade(vector<int> arr,
           const vector<pair<int, int>>& swaps,
           const vector<pair<int, int>>& ans_swaps) {
    assert(sz(ans_swaps) <= sz(swaps));

    for (int i = 0; i < sz(ans_swaps); i++) {
        if (is_sorted(begin(arr), end(arr))) {
            return;
        }
        {
            auto [u, v] = swaps[i];
            swap(arr[u], arr[v]);
        }
        {
            auto [u, v] = ans_swaps[i];
            swap(arr[u], arr[v]);
        }
    }

    assert(is_sorted(begin(arr), end(arr)));
}

int findSwapPairs(int n,
                  int p_arr[],
                  int m,
                  int swaps_x[],
                  int swaps_y[],
                  int out_p[],
                  int out_q[]) {
    vector<int> arr(p_arr, p_arr + n);

    vector<pair<int, int>> swaps(m);
    for (int i = 0; i < m; i++) {
        swaps[i] = {swaps_x[i], swaps_y[i]};
    }

    auto ans = solve(arr, vector(swaps.begin(), swaps.end() - 1));

    for (int i = 0; i < sz(ans); i++) {
        auto& [p, q] = ans[i];
        out_p[i] = p;
        out_q[i] = q;
    }

    grade(arr, swaps, ans);
    return sz(ans);
}

Subtask #1
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1 ms	340 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1 ms	340 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct