Submission #1212495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212495		NValchanov	Prisoner Challenge (IOI22_prison)	C++20	0 / 100	0 ms	324 KiB

prison

#include "prison.h"

#include <vector>

using namespace std;

const int MAXLOG = 8;

int p3[MAXLOG];

vector < vector < int > > devise_strategy(int n)
{
    int lg = 1;
    int cur = 3;

    while(cur <= n)
    {
        lg++;
        cur *= 3;
    }

    p3[0] = 1;

    for(int i = 1; i < MAXLOG; i++)
    {
        p3[i] = p3[i - 1] * 3;
    }

    vector < vector < int > > ans;

    ans.resize(3 * lg - 2 + 1);

    for(int i = 0; i <= 3 * lg - 2; i++)
    {
        ans[i].resize(n + 1, 0);
    }

    for(int sees = 1; sees <= n; sees++)
    {
        int trit = sees / p3[lg - 1];

        ans[0][sees] = trit + 1;  
    }

    for(int reads = 1; reads <= 3 * lg - 2; reads++)
    {
        int whole = reads / 3 + (bool)(reads % 3);

        if(whole % 2 == 0)
            ans[reads][0] = 0;
        else
            ans[reads][0] = 1;

        for(int sees = 1; sees <= n; sees++)
        {
            int trita;

            if(whole == lg)
                trita = 1;
            else
                trita = (reads + 2) % 3;

            int which = lg - whole;
            int tritb = (sees / p3[which]) % 3;

            if(trita < tritb)
            {
                if(whole % 2 == 0)
                    ans[reads][sees] = -2;
                else
                    ans[reads][sees] = -1;
            }
            else if(trita > tritb)
            {
                if(whole % 2 == 0)
                    ans[reads][sees] = -1;
                else
                    ans[reads][sees] = -2;
            }
            else if(whole == lg - 1)
            {
                if(sees % 3 == 1)
                {
                    ans[reads][sees] = 3 * whole + 1;
                }
                else
                {
                    int cur = whole;

                    if(sees % 3 == 0)
                        cur++;

                    if(cur % 2 == 1)
                        ans[reads][sees] = -1;
                    else
                        ans[reads][sees] = -2;
                }
            }
            else if(whole != lg - 1)
            {
                if(whole == lg)
                {
                    ans[reads][sees] = 0;
                }
                else
                {
                    int nxttrit = (sees / p3[which - 1]) % 3;

                    int writes = 3 * whole + nxttrit + 1;

                    ans[reads][sees] = writes;
                }
            }
        }
    }

    return ans;
}

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