Submission #1230310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230310		kaltspielerhy	Prisoner Challenge (IOI22_prison)	C++20	0 / 100	1095 ms	320 KiB

prison

#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
const int x = 31;

vector<int> puissance3;

int bit3(int num, int bit) {
    int multAct = bit;
    while (num > puissance3[multAct]) multAct++;
    while (multAct != bit) {
        while (num >= puissance3[multAct])
            num -= puissance3[multAct];
        multAct--;
    }

    int reponse = 0;
    while (num >= (puissance3[multAct])) {
        num -= puissance3[multAct];
        reponse++;
    }

    return reponse;
}

vector<vector<int>> devise_strategy(int N) {
    puissance3.resize(13);
    puissance3[0] = 1;
    for (int i = 1; i <= 12; i++) puissance3[i] = puissance3[i-1]*3;
    vector<vector<int>> s(x+1, vector<int>(N+1));

    int iBit = 9;
    s[0][0] = 0;
    for (int A = 1; A <= N; A++) {
        s[0][A] = bit3(A, iBit)+1;
    }

    int idx = 1;
    while (iBit >= 0) {
        for (int i = 0; i < 3; i++) {
            s[idx][0] = ((9-iBit)%2==0?1:0);
            
            int num = 1;
            while (num <= N) {
                if (bit3(num, iBit) < i) {
                    s[idx][num] = ((9-iBit+1)%2==0?-1:-2);
                }
                if (bit3(num, iBit) == i) {
                    s[idx][num] = bit3(num, iBit-1)+(9-iBit+1)*3+1;
                }
                if (bit3(num, iBit) > i) {
                    s[idx][num] = ((9-iBit+1)%2==0?-2:-1);
                }

                num++;
            }

            idx++;
        }

        iBit--;
    }
    
    // for (auto i : s) {
    //   for (auto i2 : i) {
    //     cerr << i2 << ' ';
    //   }
    //   cerr <<'\n';
    // }

    return s;
}

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