제출 #1356390

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

prison

#include <algorithm>//chatgpt
#include <vector>

using namespace std;

namespace {

int extract_digit(int value, const vector<int>& block_size, const vector<int>& radix, int depth) {
    const int zero_based = value - 1;
    return (zero_based / block_size[depth]) % radix[depth];
}

}  // namespace

vector<vector<int>> devise_strategy(int N) {
    vector<long long> best_product(61, 0);
    vector<int> previous_cost(61, -1);
    vector<int> chosen_radix(61, -1);

    best_product[0] = 1;

    for (int cost = 0; cost <= 60; ++cost) {
        if (best_product[cost] == 0) {
            continue;
        }

        for (int radix = 2; radix <= 8; ++radix) {
            int next_cost = cost + radix + 1;
            if (next_cost > 60) {
                continue;
            }

            long long next_product = best_product[cost] * radix;
            if (next_product > best_product[next_cost]) {
                best_product[next_cost] = next_product;
                previous_cost[next_cost] = cost;
                chosen_radix[next_cost] = radix;
            }
        }
    }

    int final_cost = -1;
    for (int cost = 0; cost <= 60; ++cost) {
        if (best_product[cost] >= N) {
            final_cost = cost;
            break;
        }
    }

    if (final_cost == -1) {
        return {};
    }

    vector<int> radix;
    while (final_cost > 0) {
        radix.push_back(chosen_radix[final_cost]);
        final_cost = previous_cost[final_cost];
    }
    reverse(radix.begin(), radix.end());

    const int levels = static_cast<int>(radix.size());
    vector<int> block_size(levels, 1);
    for (int i = levels - 2; i >= 0; --i) {
        block_size[i] = block_size[i + 1] * radix[i + 1];
    }

    int state_count = levels;
    vector<vector<int>> b_state(levels);
    for (int depth = 0; depth < levels; ++depth) {
        b_state[depth].resize(radix[depth]);
        for (int digit = 0; digit < radix[depth]; ++digit) {
            b_state[depth][digit] = state_count++;
        }
    }

    vector<vector<int>> strategy(state_count, vector<int>(N + 1, 0));

    for (int depth = 0; depth < levels; ++depth) {
        strategy[depth][0] = 0;
        for (int coins = 1; coins <= N; ++coins) {
            int digit = extract_digit(coins, block_size, radix, depth);
            strategy[depth][coins] = b_state[depth][digit];
        }
    }

    for (int depth = 0; depth < levels; ++depth) {
        for (int fixed_digit = 0; fixed_digit < radix[depth]; ++fixed_digit) {
            int state = b_state[depth][fixed_digit];
            strategy[state][0] = 1;

            for (int coins = 1; coins <= N; ++coins) {
                int digit = extract_digit(coins, block_size, radix, depth);
                if (digit < fixed_digit) {
                    strategy[state][coins] = -2;
                } else if (digit > fixed_digit) {
                    strategy[state][coins] = -1;
                } else if (depth + 1 < levels) {
                    strategy[state][coins] = depth + 1;
                } else {
                    strategy[state][coins] = 0;
                }
            }
        }
    }

    return strategy;
}

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