제출 #1362867

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

prison

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

vector<vector<int>> devise_strategy(int N) {
    vector<int> pow3(1, 1);
    while (pow3.back() < N) pow3.push_back(pow3.back() * 3);
    int L = (int)pow3.size() - 1;

    int S = 1 + 3 * L;
    vector<vector<int>> ans(S, vector<int>(N + 1, 0));

    auto state = [&](int pos, int dig) {
        return 1 + pos * 3 + dig;
    };

    for (int j = 1; j <= N; ++j) {
        int d = (j / pow3[L - 1]) % 3;
        ans[0][j] = state(0, d);
    }

    for (int pos = 0; pos < L; ++pos) {
        int p = L - 1 - pos;

        for (int da = 0; da < 3; ++da) {
            int id = state(pos, da);
            ans[id][0] = 1;

            for (int b = 1; b <= N; ++b) {
                int db = (b / pow3[p]) % 3;

                if (db < da) {
                    ans[id][b] = -2;
                } else if (db > da) {
                    ans[id][b] = -1;
                } else if (pos == L - 1) {
                    ans[id][b] = -1;
                } else {
                    int nd = (b / pow3[p - 1]) % 3;
                    ans[id][b] = state(pos + 1, nd);
                }
            }
        }
    }

    return ans;
}

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