제출 #1362830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1362830		erering	죄수들의 도전 (IOI22_prison)	C++20	80 / 100	5 ms	1132 KiB

prison

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

vector<vector<int>> devise_strategy(int N) {
    const int D = 8;
    auto digit = [&](int v, int pos) {
        int x = v - 1;
        int p = 1;
        for (int i = 0; i < D - 1 - pos; ++i) p *= 3;
        return (x / p) % 3;
    };

    auto id = [&](int level, int d) {
        if (level == D - 1) return 22;
        return 1 + level * 3 + d;
    };

    vector<vector<int>> s(23, vector<int>(N + 1, 0));
    s[0][0] = 0;

    for (int j = 1; j <= N; ++j) {
        s[0][j] = id(0, digit(j, 0));
    }

    for (int level = 0; level < D - 1; ++level) {
        for (int d = 0; d < 3; ++d) {
            int st = id(level, d);
            s[st][0] = (level % 2 == 0 ? 1 : 0);

            for (int j = 1; j <= N; ++j) {
                int q = digit(j, level);

                if (q < d) {
                    s[st][j] = (level % 2 == 0 ? -2 : -1);
                } else if (q > d) {
                    s[st][j] = (level % 2 == 0 ? -1 : -2);
                } else {
                    int nd = digit(j, level + 1);

                    if (level + 1 == D - 1) {
                        if (nd == 0) {
                            s[st][j] = (level % 2 == 0 ? -2 : -1);
                        } else if (nd == 2) {
                            s[st][j] = (level % 2 == 0 ? -1 : -2);
                        } else {
                            s[st][j] = id(level + 1, 1);
                        }
                    } else {
                        s[st][j] = id(level + 1, nd);
                    }
                }
            }
        }
    }

    s[22][0] = 0;
    for (int j = 1; j <= N; ++j) {
        int q = digit(j, D - 1);
        if (q == 0) s[22][j] = -1;
        else if (q == 2) s[22][j] = -2;
        else s[22][j] = -1;
    }

    return s;
}

• 서브태스크 1: 5 / 5
• 서브태스크 2: 5 / 5
• 서브태스크 3: 70 / 90