oj.uz

답안 #529270

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
529270 2022-02-22T15:02:55 Z Cyanmond 정렬하기 (IOI15_sorting) C++17
36 / 100
 1000 ms 640 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() {
    for (int step = 0; step < M; ++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 < M; ++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.0 / 8.0

# 결과 실행 시간 메모리 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 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 0 ms 292 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 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 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 0 ms 292 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 352 KB Output is correct
12 Correct 2 ms 332 KB Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 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 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 0 ms 292 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 352 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 344 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Execution timed out 1081 ms 640 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1094 ms 416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1094 ms 416 KB Time limit exceeded
2 Halted 0 ms 0 KB -