Submission #763456

#	Time	Username	Problem	Language	Result	Execution time	Memory
763456		MinaRagy06	정렬하기 (IOI15_sorting)	C++17	0 / 100	2 ms	436 KiB

sorting

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;

int findSwapPairs(int n, int _s[], int m, int x[], int y[], int p[], int q[]) {
    int s[n], ok = 1;
    for (int i = 0; i < n; i++) {
        s[i] = _s[i];
    }
    for (int i = 1; i < n; i++) {
        ok &= (s[i - 1] < s[i]);
    }
    if (ok) return 0;
    for (int i = 0; i < m; i++) {
        swap(s[x[i]], s[y[i]]);
    }
    int r = 0;
    int vis[n]{}, val[n];
    for (int i = 0; i < n; i++) val[i] = i;
    for (int st = 0; st < n; st++) {
        if (vis[st]) continue;
        int i = st;
        while (1) {
            vis[i] = 1;
            if (vis[s[i]]) break;
            int a = val[i], b = val[s[i]];
            p[r] = a, q[r] = b;
            r++;
            if (val[i] == i) {
                val[i] = b;
            }
            if (val[s[i]] == s[i]) {
                val[s[i]] = a;
            }
            i = s[i];
        }
    }
    while (r < m) {
        p[r] = 0, q[r] = 0;
        r++;
    }
    for (int i = 0; i < r; i++) {
        assert(0 <= q[i] && q[i] < n);
        assert(0 <= p[i] && p[i] < n);
        swap(s[q[i]], s[p[i]]);
    }
    for (int i = 1; i < n; i++) {
        assert(s[i - 1] < s[i]);
    }
    return r;
}
// int main() {
//     ios_base::sync_with_stdio(0), cin.tie(0);
//     int N;
//     cin >> N;
//     int S[N];
//     for (int i = 0; i < N; i++) {
//         cin >> S[i];
//     }
//     int M;
//     cin >> M;
//     int X[M], Y[M];
//     for (int i = 0; i < M; i++) {
//         cin >> X[i] >> Y[i];
//     }
//     int P[M], Q[M];
//     int R = findSwapPairs(N, S, M, X, Y, P, Q);
//     cout << R << '\n';
//     for (int i = 0; i < R; i++) {
//         cout << P[i] << ' ' << Q[i] << '\n';
//     }
//     return 0;
// }

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