제출 #701173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
701173		boris_mihov	죄수들의 도전 (IOI22_prison)	C++17	80 / 100	15 ms	1492 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;
}

inline int encode(int bit, int val)
{
    if (bit == 0) return 1;
    return 3 * bit + val - 1;
}

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(23);
    s[0].resize(n + 1, 0);
    for (int x = 1 ; x <= n ; ++x)
    {
        s[0][x] = encode(7, getBit(x, 7));
    }

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

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

                if (bit == 0) continue;
                if (bit == 1)
                {
                    if (getBit(money, bit - 1) == 0)
                    {
                        if (bit & 1) s[encode(bit, val)][money] = -1;
                        s[encode(bit, val)][money] = -2;
                        continue;
                    }

                    if (getBit(money, bit - 1) == 2)
                    {
                        if (bit & 1) s[encode(bit, val)][money] = -2;
                        s[encode(bit, val)][money] = -1;
                        continue;
                    }
                }

                s[encode(bit, val)][money] = encode(bit - 1, getBit(money, bit - 1));
            }
        }
    }
    
    return s;
}

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