Submission #702927

#	Time	Username	Problem	Language	Result	Execution time	Memory
702927		boris_mihov	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	12 ms	1820 KiB

prison

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

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

std::vector <int> bitwise[MAXN];
std::vector <int> divide = {3, 3, 3, 3, 3, 2, 2, 1};
inline int encode(int bit, int val)
{
    int sum = 1;
    for (int i = 0 ; i < bit ; ++i)
    {
        sum += divide[i];
    }

    return sum + val;
}

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

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

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

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

        bitwise[num].push_back(1);
        getBitwise(num, l + len + 1, r - 1, where + 1);
        return;
    }

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

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

    bitwise[num].push_back(2);
    getBitwise(num, l + 2*len + 1, r - 1, where + 1);
}

std::vector <std::vector <int>> s;
std::vector <std::vector <int>> devise_strategy(int n) 
{
    for (int i = 1 ; i <= n ; ++i)
    {
        getBitwise(i, 1, n, 0);
    }

    s.resize(21);
    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 < divide.size() ; ++bit)
    {
        for (int val = 0 ; val < divide[bit] ; ++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;
                }

                if (encode(bit + 1, bitwise[money][bit + 1]) == 21)
                {
                    s[encode(bit, val)][money] = ((bit & 1) ? -1 : -2);
                    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:102:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int bit = 0 ; bit < divide.size() ; ++bit)
      |                        ~~~~^~~~~~~~~~~~~~~
prison.cpp:110:43: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |                 if (bitwise[money].size() <= bit)
      |                     ~~~~~~~~~~~~~~~~~~~~~~^~~~~~

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