Submission #702876

#	Time	Username	Problem	Language	Result	Execution time	Memory
702876		boris_mihov	Prisoner Challenge (IOI22_prison)	C++17	90 / 100	16 ms	1748 KiB

prison

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

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

int power[MAXN];
std::vector <int> bitwise[MAXN];
inline int encode(int bit, int val)
{
    return 3 * bit + val + 1;
}

void getBitwise(int num, int l, int r)
{
    if (num == l)
    {
        bitwise[num].push_back(-1);
        return;
    }

    if (num == r)
    {
        bitwise[num].push_back(-2);
        return;
    }

    int len = (r - l - 1) / 3 + ((r - l - 1) % 3 == 2);
    if (num <= l + len)
    {
        bitwise[num].push_back(0);
        getBitwise(num, l + 1, l + len);
        return;
    }

    if (num <= l + 2 * len)
    {
        bitwise[num].push_back(1);
        getBitwise(num, l + len + 1, l + 2*len);
        return;
    }

    bitwise[num].push_back(2);
    getBitwise(num, l + 2*len + 1, r - 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;
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        getBitwise(i, 1, n);
    }

    s.resize(22);
    s[0].resize(n + 1, 0);
    for (int x = 1 ; x <= n ; ++x)
    {
        if (bitwise[x][0] < 0)
        {
            s[0][x] = bitwise[x][0];
            continue;
        }
        
        s[0][x] = encode(0, bitwise[x][0]);
    }

    for (int bit = 0 ; bit <= 6 ; ++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 (bitwise[money].size() <= bit)
                {
                    s[encode(bit, val)][money] = -1;
                    continue;
                }

                int currBit = bitwise[money][bit];
                if (currBit == -1)
                {
                    s[encode(bit, val)][money] = ((bit & 1) ? -1 : -2);
                    continue;
                }

                if (currBit == -2)
                {
                    s[encode(bit, val)][money] = ((bit & 1) ? -2 : -1);
                    continue;
                }
                
                if (currBit != val)
                {
                    s[encode(bit, val)][money] = ((currBit < val) ^ (bit & 1) ? -2 : -1);
                    continue;
                }

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

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

                s[encode(bit, val)][money] = encode(bit + 1, bitwise[money][bit + 1]);
            }
        }
    }
    
    return s;
}

Compilation message (stderr)

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:87:43: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |                 if (bitwise[money].size() <= bit)
      |                     ~~~~~~~~~~~~~~~~~~~~~~^~~~~~

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