Submission #1362229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1362229		activedeltorre	Prisoner Challenge (IOI22_prison)	C++20	80 / 100	5 ms	1092 KiB

prison

#include "prison.h"

#include <vector>

using namespace std;
int state(int bit,int cat)
{
    return bit+cat*7+1;
}
int get_bit(int state)
{
    return (state-1)%7;
}
int get_cat(int state)
{
    return (state-1)/7;
}
std::vector<std::vector<int>> devise_strategy(int N)
{
    int maxnumber=24,n=N;
    vector<vector<int>>rasp;
    rasp.resize(23);
    int pow3[10]= {1,3,9,27,81,81*3,81*9,81*27,81*81};
    for(int i=0; i<=22; i++)
    {
        rasp[i].resize(N+1);
    }
    rasp[0][0]=0;
    for(int i=1; i<=n; i++)
    {
        rasp[0][i]=state(0,i/pow3[7]);
    }
    for(int i=1; i<=21; i++)
    {
        int bit=get_bit(i);
        int cat=get_cat(i);
        if(bit%2==0)
        {
            rasp[i][0]=1;
            for(int j=1; j<=n; j++)
            {
                int cat2=j/pow3[7-bit];
                cat2=cat2%3;
                if(cat2==cat)
                {
                    int catnxt=j/pow3[6-bit];
                    catnxt%=3;
                    if(bit==6)
                    {
                        if(catnxt==0)
                        {
                            rasp[i][j]=-2;
                        }
                        else if(catnxt==2)
                        {
                            rasp[i][j]=-1;
                        }
                        else
                        {
                            rasp[i][j]=22;
                        }
                    }
                    else
                    {
                        rasp[i][j]=state(bit+1,catnxt);
                    }
                }
                else if(cat2>cat)
                {
                    rasp[i][j]=-1;
                }
                else if(cat2<cat)
                {
                    rasp[i][j]=-2;
                }
            }
        }
        else
        {
            rasp[i][0]=0;
            for(int j=1; j<=n; j++)
            {
                int cat2=j/pow3[7-bit];
                cat2=cat2%3;
                if(cat2==cat)
                {
                    int catnxt=j/pow3[6-bit];
                    catnxt%=3;
                    rasp[i][j]=state(bit+1,catnxt);
                }
                else if(cat2<cat)
                {
                    rasp[i][j]=-1;
                }
                else if(cat2>cat)
                {
                    rasp[i][j]=-2;
                }
            }
        }
    }
    rasp[22][0]=0;
    for(int j=1; j<=n; j++)
    {
        int bit=j%3;
        if(bit==0)
        {
            rasp[22][j]=-1;
        }
        else
        {
            rasp[22][j]=-2;
        }
    }
    return rasp;
}

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