Submission #1222633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222633		totoro	Prisoner Challenge (IOI22_prison)	C++20	65 / 100	7 ms	1096 KiB

prison

#include "prison.h"

#include <vector>

std::vector<std::vector<int>> devise_strategy(int N) {
    std::vector<std::vector<int>> strategy(25, std::vector<int>(N + 1));
    for (int val = 0; val < 25; ++val) {
        if (val == 0) {
            strategy[val][0] = 0;
            for (int inbaga = 1; inbaga <= N; ++inbaga) strategy[val][inbaga] = 1 + (inbaga >= 4096);
            continue;
        }
        int bitnum = 12 - (val - 1) / 2;
        int state = (val - 1) % 2;
        strategy[val][0] = ~bitnum & 1;
        for (int inbag = 1; inbag <= N; ++inbag) {
            int curbit = (inbag >> bitnum) & 1;
            if (curbit != state) {
                strategy[val][inbag] = -1 - (state != (bitnum & 1));
                continue;
            }
            int newbitnum = bitnum - 1;
            if (newbitnum == 0) {
                strategy[val][inbag] = -1 - (inbag & 1);
                continue;
            }
            strategy[val][inbag] = val + 2 - state + ((inbag >> newbitnum) & 1);
        }
    }
    return strategy;
}

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