Submission #1247912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247912		adrilen	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	7 ms	1092 KiB

prison

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

int powers[10] = {0 };

std::vector<std::vector<int>> devise_strategy(int N) {
    powers[0] = 1;
    for (int i = 1; i < 10; i++) powers[i] = powers[i - 1] * 3;


    int x = 22;
    vector<vector<int>> output(x + 1, vector<int>(N + 1));

    output[1][0] = 1; // Siste bit i A er 1, så sjekk siste bit i B
    for (int i = 1; i <= N; i++) {
        if (i % powers[1] == 0) output[1][i] = -2;
        else if (i % powers[1] == 2) output[1][i] = -1;
    }

    int val, under_val;
    // Sjekk A
    output[2][0] = output[3][0] = output[4][0] = 0;
    for (int i = 1; i <= N; i++)
    {
        val = (i % powers[2]) / powers[1];
        under_val = (i % powers[1]);
        if (val == 0) 
        {
            output[3][i] = output[4][i]= -1; // A er minst
            
            if (under_val == 0) output[2][i] = -1;
            else if (under_val == 2) output[2][i] = -2;
            else output[2][i] = 1;
        } else if (val == 1)
        {
            output[2][i] = -2;
            output[4][i] = -1;
            if (under_val == 0) output[3][i] = -1;
            else if (under_val == 2) output[3][i] = -2;
            else output[3][i] = 1;
        } else {
            output[2][i] = output[3][i] = -2;

            if (under_val == 0) output[4][i] = -1;
            else if (under_val == 2) output[4][i] = -2;
            else output[4][i] = 1;
        }
    }

    int current = 2;
    for (int y = 5; y < x; y+= 3)
    {
        output[y][0]= output[y + 1][0] = output[y+2][0] = current - 1;

        for (int i = 1; i <= N; i++)
        {
            val = (i % powers[y / 3 + 2]) / powers[y / 3 + 1];
            under_val = (i % powers[y / 3 + 1]) / powers[y / 3];

            if (val == 0)
            {
                output[y + 1][i] = output[y + 2][i] = -current;
                output[y][i] = y - 3 + under_val;
            } else if (val == 1){
                output[y][i] = -(current % 2 + 1);
                output[y+2][i] = -current;

                output[y+1][i] = y - 3 + under_val;
            } else {
                output[y][i] = output[y + 1][i] = -(current % 2 + 1);
                output[y+2][i] = y - 3 + under_val;
            }
        } 
        current = current% 2 + 1;
    }
    
    output[0][0] = (output.back()[0] + 1) % 2;
    for (int i = 1; i <= N; i++)
    {
        output[0][i] = 20 + i / powers[7];
    }

    // int indx = 0;
    // for (auto y : output)
    // {
    //     cout << indx++ << "\t";
    //     for (int i : y) cout <<i << " ";
    //     cout << "\n";
    // }

    return output;
}

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