Submission #767557

#	Time	Username	Problem	Language	Result	Execution time	Memory
767557		mousebeaver	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	12 ms	1076 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

const int digits = 8;

string ternary(int a)
{
    string output = "";
    for(int i = 0; i < digits; i++)
    {
        output = (char) ((int) '0' + (a%3)) + output;
        a /= 3;
    }
    return output;
}

std::vector<std::vector<int>> devise_strategy(int N) 
{
    vector<string> t(N);
    for(int i = 1; i <= N; i++)
    {
        t[i-1] = ternary(i);
    }
    int m = 22;
    //cout<<"Test: "<<t[2186]<<", "<<t[2180]<<endl;

    vector<vector<int>> output(m+1, vector<int> (N+1));
    //First look:
    output[0][0] = 1;
    for(int j = 1; j <= N; j++)
    {
        int pre = (int) t[j-1][0] - (int) '0';
        output[0][j] = 1+pre;
    }

    for(int i = 1; i <= 21; i++)
    {

        //Compare with the previous check
        int bit = (i-1)/3; //Previous bit
        int pre = (i-1)%3;
        output[i][0] = bit%2;

        for(int j = 1; j <= N; j++)
        {
            int post = (int) t[j-1][bit] - (int) '0';
            if(pre < post)
            {
                output[i][j] = (bit%2==0) ? -2 : -1;
            }
            else if(pre == post)
            {
                //Prepare check of next bit
                post = (int) t[j-1][bit+1] - (int) '0';
                if(bit < 6)
                {
                    output[i][j] = 1 + post + (bit+1)*3;
                }
                else
                {
                    if(post == 0)
                    {
                        output[i][j] = -1;
                    }
                    else if(post == 1)
                    {
                        output[i][j] = m;
                    }
                    else
                    {
                        output[i][j] = -2;
                    }
                }
            }
            else
            {
                output[i][j] = (bit%2==0) ? -1 : -2;
            }
        }
    }

    //Last bit!
    output[m][0] = 1;
    for(int i = 1; i <= N; i++)
    {
        if(t[i-1][7] == '0')
        {
            output[m][i] = -2;
        }
        else
        {
            output[m][i] = -1;
        }
    }

    return output;
}

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