Submission #633198

#	Time	Username	Problem	Language	Result	Execution time	Memory
633198		JeanBombeur	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	12 ms	1368 KiB

prison

#include "prison.h"
#include <vector>
#include <cstdio>
using namespace std;

//  <|°_°|>

//  M. Broccoli

//  The hardest choices require the strongest wills

//  What is better - to be born good, or to overcome your evil nature with great effort ?

const int SIZE = (20);
const int MAXIMUM = (5001);

int Answer[SIZE + 1][MAXIMUM];

int done = 0;

int IsSmaller(int bag) {
    return bag ? -2 : -1;
}

void Fill(int number, int left, int right) {
    int rest = 0, cut = 3, bag = 0;
    if (number > 5)
        bag = (number / 3) & 1, rest = number % 3;
    else if (number > 1)
        bag = (number >> 2) & 1, rest = number & 1, cut = 2;
    else
        bag = 1, cut = 1;
    
    Answer[number][0] = bag;
    Answer[number][left ++] = IsSmaller(bag);
    Answer[number][-- right] = IsSmaller(!bag);
    
    if (!number)
        left --, right ++;
    
    int mini = left + ((right - left) * rest + cut - 1) / cut;
    int maxi = left + ((right - left) * (rest + 1) + cut - 1) / cut;
    for (int i = left; i <= mini; i ++)
    {
        Answer[number][i] = IsSmaller(bag);
    }
    for (int i = maxi - 1; i < right; i ++)
    {
        Answer[number][i] = IsSmaller(!bag);
    }
    int nv = number ? number - rest : 21;
    if (number == 1)
        return;
    if (!number)
        cut = 3;
    if (number == 2 || number == 3)
        cut = 1;
    if (number / 3 == 2)
        cut = 2;
    nv -= cut;
    mini ++, maxi --;
    for (int i = mini; i < maxi; i ++)
    {
        Answer[number][i] = nv + (i - mini) * cut / (maxi - mini);
    }
    for (int i = 0; i < cut; i ++)
    {
        Fill(nv + i, mini - 1, maxi + 1);
    }
    return;
}

vector <vector <int>> devise_strategy(int maximum) {
    if (!done)
        Fill(0, 1, MAXIMUM), done = 1;
    
    vector <vector <int>> ans(SIZE + 1);
    for (int i = 0; i <= SIZE; i ++)
    {
        ans[i].resize(maximum + 1, 0);
        for (int j = 0; j <= maximum; j ++)
            ans[i][j] = Answer[i][j];
    }
    return ans;
}

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