Submission #1362073

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

prison

#include "prison.h"

#include <cassert>
#include <cstdio>

#include <string>
#include <vector>
#include <iostream>


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

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