Submission #767474

#	Time	Username	Problem	Language	Result	Execution time	Memory
767474		mousebeaver	Prisoner Challenge (IOI22_prison)	C++17	51.50 / 100	13 ms	1300 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) 
{
    //cout<<"Test: "<<ternary(2187)<<", "<<ternary(2181)<<endl;
    vector<string> t(N);
    for(int i = 1; i <= N; i++)
    {
        t[i-1] = ternary(i);
    }
    int m = 29;

    vector<vector<int>> output(m+1, vector<int> (N+1));
    for(int i = 0; i <= 6; i++)
    {
        //Inspect bag A:
        output[i][0] = 0;
        //Results:
        for(int j = 1; j <= N; j++)
        {
            output[i][j] = 8 + 3*i + (int) t[j-1][i] - (int) '0';
        }
    }

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

    for(int i = 8; i <= 28; i++)
    {
        output[i][0] = 1;
        int bit = (i-8)/3;
        int pre = (i-8)%3;

        for(int j = 1; j <= N; j++)
        {
            int post = (int) t[j-1][bit] - (int) '0';

            if(pre < post)
            {
                output[i][j] = -1;
            }
            else if(pre == post)
            {
                output[i][j] = bit+1;
            }
            else
            {
                output[i][j] = -2;
            }
        }
    }

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

    return output;
}

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