Submission #721621

#	Time	Username	Problem	Language	Result	Execution time	Memory
721621		bin9638	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	14 ms	1492 KiB

prison

#include <bits/stdc++.h>

#ifndef SKY
#include "prison.h"
#endif // SKY

using namespace std;

#define N 100010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,ll>
#define pb push_back

vector<vector<int>>kq;

#ifdef SKY
int A,B;

void answer(int x)
{
    if(x==-1)
    {
        cout<<"A";
        return;
    }
    if(x==-2)
    {
        cout<<"B";
        return;
    }
    if(kq[x][0]==0)
    {
        answer(kq[x][A]);
    }else
    {
        answer(kq[x][B]);
    }
}
#endif // SKY

int get_num(int x,int h)
{
    for(int i=1;i<=h;i++)
        x/=3;
    return x%3;
}

vector<vector<int>> devise_strategy(int n)
{
    kq.resize(23,vector<int>(n+1,0));
    for(int i=1;i<=n;i++)
        kq[0][i]=get_num(i,7)+1;
    int dem=0;
    for(int id=0,h=7;h>=0;h--)
    {
        id^=1;
        dem+=3;
        if(h==0)
        {
            kq[22][0]=id;
            for(int i=1;i<=n;i++)
                if(get_num(i,h)==0)
                {
                    if(id==0)
                        kq[22][i]=-1;
                            else kq[22][i]=-2;
                }
            for(int i=1;i<=n;i++)
                if(get_num(i,h)==2)
                {
                    if(id==0)
                        kq[22][i]=-2;
                            else kq[22][i]=-1;
                }
            continue;
        }
        for(int du=0;du<3;du++)
        {
            kq[dem-2+du][0]=id;
            if(id==0)
            {
                for(int i=1;i<=n;i++)
                    if(get_num(i,h)<du)
                        kq[dem-2+du][i]=-1;
                for(int i=1;i<=n;i++)
                    if(get_num(i,h)>du)
                        kq[dem-2+du][i]=-2;
                for(int i=1;i<=n;i++)
                    if(get_num(i,h)==du)
                    {
                        if(h==1)
                        {
                            if(get_num(i,h-1)==0)
                                kq[dem-2+du][i]=-1;
                             if(get_num(i,h-1)==2)
                                kq[dem-2+du][i]=-2;
                            if(get_num(i,h-1)==1)
                            {
                                kq[dem-2+du][i]=22;
                            }
                            continue;
                        }
                        kq[dem-2+du][i]=dem+get_num(i,h-1)+1;
                    }
            }else
            {
                 for(int i=1;i<=n;i++)
                    if(get_num(i,h)<du)
                        kq[dem-2+du][i]=-2;
                for(int i=1;i<=n;i++)
                    if(get_num(i,h)>du)
                        kq[dem-2+du][i]=-1;
                for(int i=1;i<=n;i++)
                    if(get_num(i,h)==du)
                    {
                        if(h==1)
                        {
                            if(get_num(i,h-1)==0)
                                kq[dem-2+du][i]=-2;
                             if(get_num(i,h-1)==2)
                                kq[dem-2+du][i]=-1;
                            if(get_num(i,h-1)==1)
                            {
                                kq[dem-2+du][i]=22;
                            }
                            continue;
                        }
                        kq[dem-2+du][i]=dem+get_num(i,h-1)+1;
                    }
            }
        }
    }
    return kq;
}


#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n>>A>>B;
    vector<vector<int>>s=devise_strategy(n);
    answer(0);
    return 0;
}
#endif

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