oj.uz

Submission #529266

# Submission time Handle Problem Language Result Execution time Memory
529266 2022-02-22T14:55:32 Z Cyanmond Sorting (IOI15_sorting) C++17
16 / 100
 600 ms 412 KB 
// 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() {
    // c = N
    for (int step = 0; step < N; ++step) {
        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;
            }
        }
    }
	assert((int)P.size() == N);
    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
0 / 8.0

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

Subtask #2
0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #4
0 / 18.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 26.0

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