Submission #1055246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055246		vjudge1	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	17 ms	1116 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;


vector<vi> devise_strategy(int n) {
    int m = 24; 
    vector<vi> S(m + 1, vi(n + 1, 0));
    auto get_vec = [&](int val) -> vi {
        vi V;
        for(int i = 0; i < 8; ++i) {
            V.push_back(val % 3);
            val /= 3;
        }
        reverse(V.begin(), V.end());
        return V;
    };

    auto combina = [&](int id, int val) {
        int re = (id - 1) * 3 + val + 1;
        return re;
    };

    auto desc = [&](int v) -> ii {
        int id = 1 + (v - 1) / 3;
        int val = (v - 1) % 3;
        return {id, val};
    };
    


    //pentru 0
    S[0][0] = 0;
    for(int i = 1; i <= n; ++i)
        S[0][i] = combina(1, get_vec(i)[0]);

    //restul
    for(int i = 1; i <= m; ++i) {
        auto [id, val] = desc(i);
        if(id & 1) S[i][0] = 1;
        else S[i][0] = 0;
        for(int v = 1; v <= n; ++v) {
            int v2 = get_vec(v)[id - 1];
            if(v2 != val) {
                int mai_mic = (val < v2) ^ S[i][0];
                if(mai_mic) S[i][v] = -2;
                else S[i][v] = -1;
            } else {
                if(id == 8) S[i][v] = -2;
                else S[i][v] = combina(id + 1, get_vec(v)[id]);
            }
        }
    }

    return S;
}

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