Submission #858548

#	Time	Username	Problem	Language	Result	Execution time	Memory
858548		HubertL	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	35 ms	1188 KiB

prison

#include <bits/stdc++.h>
using namespace std;
//author: Hubert Lukasik

int state_to_board[28] = {-10, 1, 2, 3, 4, 5, 6, 7, -10, -10, -10, 8, 9, 10, 11, 12, 13, 14, 15, -10, -10, 16, 17, 18, 19, 20, 21, 22};
int board_to_state[23] = {-1, 1, 2, 3, 4, 5, 6, 7, 11, 12, 13, 14, 15, 16, 17, 18, 21, 22, 23, 24, 25, 26, 27};

int trenary(int x, int which_digit)
{
    string res = "";

    while(x > 0)
    {
        res = char('0' + x % 3) + res;
        x = x / 3;
    }

    while(res.length() < 8)
        res = '0' + res;

    return int(res[which_digit - 1] - '0');

}

vector<vector<int>> devise_strategy(int N)
{
    vector<vector<int>> ans;
    vector <int> pom;

    for(int i = 0; i < N+1; ++i)
        pom.push_back(-10);

    for(int i = 0; i <= 22; ++i)
    {
        ans.push_back(pom);
    }


    //column 0

    for(int i = 0; i <= 7; ++i)
        ans[i][0] = i % 2;
    
    for(int i = 8; i <= 22; ++i)
        ans[i][0] = (i % 2 + 1) % 2;
    
    //row 0

    ans[0][1] = -1;
    ans[0][N] = -2;
    for(int n = 2; n < N; ++n)
        ans[0][n] = state_to_board[trenary(n, 1)*10 + 1];
    
    //the rest of rows

    for(int r = 1; r <= 22; ++r)
    {
        if(ans[r][0] == 0)
        {
            ans[r][1] = -1;
            ans[r][N] = -2;
        }

        else
        {
            ans[r][1] = -2;
            ans[r][N] = -1;
        }

        int prev_pos = board_to_state[r] % 10;
        int prev_digit = board_to_state[r] / 10;

        for(int n = 2; n < N; ++n)
        {
            int digit = trenary(n, prev_pos);
            
            if(digit < prev_digit)
            {
                if(ans[r][0] == 0)
                    ans[r][n] = -1;     

                else
                    ans[r][n] = -2;
            }

            else if(digit > prev_digit)
            {
                 if(ans[r][0] == 0)
                    ans[r][n] = -2;     

                else
                    ans[r][n] = -1;
            }

            else
            {
                int act_digit = trenary(n, prev_pos + 1);

                int state = 10 * act_digit + prev_pos + 1;

                if(state == 8)
                {
                    if(ans[r][0] == 0)
                        ans[r][n] = -1;
                    else
                        ans[r][n] = -2;
                }

                else if(state == 28)
                {
                    if(ans[r][0] == 0)
                        ans[r][n] = -2;
                    else
                        ans[r][n] = -1;
                }

                else
                    ans[r][n] = state_to_board[state];
            }
        }
    }

    return ans;
}

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