oj.uz

Submission #763456

# Submission time Handle Problem Language Result Execution time Memory
763456 2023-06-22T10:22:50 Z MinaRagy06 Sorting (IOI15_sorting) C++17
0 / 100
 2 ms 436 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 296 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 296 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 296 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 436 KB Output isn't correct
2 Halted 0 ms 0 KB -