Submission #769457

#	Time	Username	Problem	Language	Result	Execution time	Memory
769457		mousebeaver	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	10 ms	1000 KiB

prison

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

std::vector<std::vector<int>> devise_strategy(int N)
{
    int n = 5000;
    vector<int> range = {5000, 1666, 555, 185, 61, 20, 6, 2}; //Sizes of the blocks (7 elements)
    vector<vector<int>> output(21, vector<int> (n+1));

    for(int i = 0; i <= 20; i++)
    {
        int bit = (i+2)/3;
        output[i][0] = bit%2;
        int indval = (i == 0) ? 0 : (i-1)%3; //Val of bit according to index i

        for(int j = 1; j <= n; j++)
        {
            int k = j; //Value in range from 1 to range[bit]
            int val = 0; //Value of the previous bit
            for(int a = 0; a < bit; a++)
            {
                k--; //We can exclude the smallest value
                if(k <= 0)
                {
                    break;
                }
                val = (k-1)/range[a+1];
                k = 1+(k-1)%range[a+1]; //Break down to the new range
            }

            if(k <= 0)
            {
                output[i][j] = -1-(bit%2);
                continue;
            }

            if(val < indval || (val == indval && k == 1))
            {
                //Current bag is smaller
                output[i][j] = -1-(bit%2);
            }
            else if(val > indval || (val == indval && k == range[bit]))
            {
                //Other bag is smaller
                output[i][j] = -2+(bit%2);
            }
            else
            {
                //Answer lies in the next block!
                k--;
                int nval = (k-1)/range[bit+1]; //Value of the next bit
                output[i][j] = 3*bit + 1 + nval;
            }
        }
    }

    for(int i = 0; i <= 20; i++)
    {
        while((int) output[i].size() > N+1)
        {
            output[i].pop_back();
        }
    }

    return output;
}

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