제출 #1212476

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1212476		NValchanov	죄수들의 도전 (IOI22_prison)	C++20	65 / 100	7 ms	1096 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 + 1);

    for(int i = 0; i <= 3 * lg; 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; 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 = (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)
                {
                    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: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 55 / 90