Submission #980333

#	Time	Username	Problem	Language	Result	Execution time	Memory
980333		sleepntsheep	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	12 ms	1192 KiB

prison

#include "prison.h"

#include <vector>

std::vector<std::vector<int>> devise_strategy(int N) {
    constexpr int B = 3, X = 22;
    std::vector<std::vector<int> > s(X+1, std::vector<int>(N+1));

    auto get = [&](int x, int i)
    {
        while(i--) x/=B;
        return x%B;
    };

    auto write = [&](int at,int j,int x) { s[at][j] = x; };
    write(0, 0, 0);
    for(int i=1;i<=N;++i)
    {
        int d=get(i, 7);
        write(0, i, 1+7*B+d -2);
    }

    for(int read=1;read<=X;++read)
    {
        auto write_ = [&](int j,int x) { write(read,j,x); };

        int at=(read-1 +2)/B;
        int dd=(read-1 +2)%B;
        int turn=at%2==1 ? 'B':'A';

        if(read==1)dd=1;

        if(turn=='B')
            write_(0, 1);
        else
            write_(0, 0);

        for(int i=1;i<=N;++i)
        {
            int ee=get(i,at);

            if (at==0)
            {
                if(ee==2)
                {
                    write_(i, turn == 'B' ? -1 : -2);
                }
                else if(ee==0)
                {
                    write_(i, turn == 'B' ? -2 : -1);
                }
                else
                {
                    write_(i, 1);
                }
            }
            else
            {
                int ff=get(i,at-1);
                if(ee==dd)
                {
                    if(at-1==0)
                    {
                        if(ff==2)
                            write_(i, turn == 'B' ? -1 : -2);
                        else if(ff==0)
                            write_(i, turn == 'B' ? -2 : -1);
                        else
                            write_(i, 1);
                    }
                    else
                    {
                        write_(i, 1+(at-1)*B+ff -2);
                    }
                }
                else
                {
                    if(turn == 'B') write_(i, ee>dd?-1:-2);
                    else write_(i, ee>dd?-2:-1);
                }
            }
        }
    }

    return s;
}

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