Submission #701172

#	Time	Username	Problem	Language	Result	Execution time	Memory
701172		boris_mihov	죄수들의 도전 (IOI22_prison)	C++17	65 / 100	18 ms	1624 KiB

prison

#include "prison.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 5000 + 10;
const int INF  = 1e9;

int power[MAXN];
inline int getBit(int num, int bit)
{
    return (num / power[bit]) % 3;
}

std::vector <std::vector <int>> s;
std::vector <std::vector <int>> devise_strategy(int n) 
{
    power[0] = 1;
    for (int i = 1 ; i <= 8 ; ++i)
    {
        power[i] = power[i - 1] * 3;
    }

    s.resize(25);
    s[0].resize(n + 1, 0);
    for (int x = 1 ; x <= n ; ++x)
    {
        s[0][x] = 22 + getBit(x, 7);
    }

    for (int bit = 0 ; bit <= 7 ; ++bit)
    {
        for (int val = 0 ; val <= 2 ; ++val)
        {
            s[3 * bit + val + 1].resize(n + 1, 0);
            s[3 * bit + val + 1][0] = (bit & 1);
            for (int money = 1 ; money <= n ; ++money)
            {
                if (getBit(money, bit) < val)
                {
                    if (bit & 1) s[3 * bit + val + 1][money] = -2;
                    else s[3 * bit + val + 1][money] = -1;
                    continue;
                }

                if (getBit(money, bit) > val)
                {
                    if (bit & 1) s[3 * bit + val + 1][money] = -1;
                    else s[3 * bit + val + 1][money] = -2;
                    continue;
                }

                if (bit == 0) continue;
                s[3 * bit + val + 1][money] = 3 * (bit - 1) + getBit(money, bit - 1) + 1;
            }
        }
    }
    
    return s;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 55 / 90