Submission #705318

#	Time	Username	Problem	Language	Result	Execution time	Memory
705318		danikoynov	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	13 ms	1508 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>
using namespace std;


vector < vector < int > > strategy;
int pw[10], _N, state_index[10][3];
const int maxbit = 8;

int create_state(int state, int bit, int val, int left, int right)
{
    ///cout << state << " " << bit << " " << val << endl;
    vector < int > cur_strategy(_N + 1);
    if (bit == 0)
    {
        cur_strategy[0] = 0;
        for (int j = 1; j <= _N; j ++)
        {
            if (j % 3 > val)
                cur_strategy[j] = -2;
            else
                cur_strategy[j] = -1;
        }
        strategy[state] = cur_strategy;
        return state;
    }

    int mid1 = -1, mid2 = -1;
    for (int j = right; j >= left; j --)
    {
        int val = ((j % pw[bit]) / pw[bit - 1]);
        if (val == 2)
            mid2 = j;
        if (val == 1)
            mid1 = j;
    }


    if (bit % 2 == 1)
    {
        cur_strategy[0] = 1;

        for (int j = 1; j <= _N; j ++)
        {
                        if (j == left)
            {
                cur_strategy[j] = -2;
                continue;
            }
            if (j == right)
            {
                cur_strategy[j] = -1;
                continue;
            }
            int cur_val = ((j % pw[bit + 1]) / pw[bit]);

            if (cur_val < val)
                cur_strategy[j] = -2;
            else if (cur_val > val)
                cur_strategy[j] = -1;
            else
            {
                cur_val = ((j % pw[bit]) / pw[bit - 1]);
                if (bit == 1)
                {
                    if (cur_val == 0)
                    {
                        cur_strategy[j] = -2;
                        continue;
                    }
                    if (cur_val == 2)
                    {
                        cur_strategy[j] = -1;
                        continue;
                    }

                }
                if (cur_val == 0)
                {
                    if (state_index[bit - 1][0] == -1)
                    {
                        strategy.emplace_back();
                        state_index[bit - 1][0] = create_state(strategy.size() - 1, bit - 1, 0, left, mid1 - 1);
                    }
                    cur_strategy[j] = state_index[bit - 1][0];
                }
                else if (cur_val == 1)
                {
                    if (state_index[bit - 1][1] == -1)
                    {
                        strategy.emplace_back();
                        state_index[bit - 1][1] = create_state(strategy.size() - 1, bit - 1, 1, mid1, mid2 - 1);
                    }
                    cur_strategy[j] = state_index[bit - 1][1];
                }
                else
                {
                    if (state_index[bit - 1][2] == -1)
                    {
                        strategy.emplace_back();
                        state_index[bit - 1][2] = create_state(strategy.size() - 1, bit - 1, 2, mid2, right);
                    }
                    cur_strategy[j] = state_index[bit - 1][2];
                }
            }
        }

    }
    else
    {
        cur_strategy[0] = 0;

        for (int j = 1; j <= _N; j ++)
        {
            if (j == left)
            {
                cur_strategy[j] = -1;
                continue;
            }
            if (j == right)
            {
                cur_strategy[j] = -2;
                continue;
            }
            int cur_val = ((j % pw[bit + 1]) / pw[bit]);
            ///cout << state << " --- " << bit << " " << " " << cur_val << endl;
            if (cur_val < val)
            {
                ///cout << "here " << bit << " " << val << " " << cur_val << endl;
                cur_strategy[j] = -1;
            }
            else if (cur_val > val)
            {
                ///cout << "there " << bit << " " << val << " " << cur_val << endl;
                cur_strategy[j] = -2;
            }
            else
            {
                cur_val = ((j % pw[bit]) / pw[bit - 1]);
                if (cur_val == 0)
                {
                    if (state_index[bit - 1][0] == -1)
                    {
                        strategy.emplace_back();
                        state_index[bit - 1][0] = create_state(strategy.size() - 1, bit - 1, 0, left, mid1 - 1);
                    }
                    cur_strategy[j] = state_index[bit - 1][0];
                }
                else if (cur_val == 1)
                {
                    if (state_index[bit - 1][1] == -1)
                    {
                        strategy.emplace_back();
                        state_index[bit - 1][1] = create_state(strategy.size() - 1, bit - 1, 1, mid1, mid2 - 1);
                    }
                    cur_strategy[j] = state_index[bit - 1][1];
                }
                else
                {
                    if (state_index[bit - 1][2] == -1)
                    {
                        strategy.emplace_back();
                        state_index[bit - 1][2] = create_state(strategy.size() - 1, bit - 1, 2, mid2, right);
                    }
                    cur_strategy[j] = state_index[bit - 1][2];
                }
            }
        }
    }

    strategy[state] = cur_strategy;
    return state;

}

void init_state()
{
    vector < int > base(_N + 1);
    strategy.emplace_back();
    base[0] = 0;
    int mid1 = 0, mid2 = 0;
    for (int j = _N; j > 0; j --)
    {
                int val = (j % pw[maxbit]) / pw[maxbit - 1];
                if (val == 1)
                    mid1 = j;
                if (val == 2)
                    mid2 = j;
    }
    for (int j = 1; j <= _N; j ++)
    {
        int val = (j % pw[maxbit]) / pw[maxbit - 1];
        if (val == 0)
        {
            if (state_index[7][0] == -1)
            {
                strategy.emplace_back();
                state_index[7][0] = create_state(strategy.size() - 1, 7, 0, 1, mid1 - 1);
            }
            base[j] = state_index[7][0];
        }
        else if (val == 1)
        {
            if (state_index[7][1] == -1)
            {
                strategy.emplace_back();
                state_index[7][1] = create_state(strategy.size() - 1, 7, 1, mid1, mid2 - 1);
            }
            base[j] = state_index[7][1];
        }
        else
        {
            if (state_index[7][2] == -1)
            {
                strategy.emplace_back();
                state_index[7][2] = create_state(strategy.size() - 1, 7, 2, mid2, 5000);
            }
            base[j] = state_index[7][2];
        }
    }

    strategy[0] = base;
}
vector<std::vector<int>> devise_strategy(int N)
{
    _N = N;
    for (int i = 0; i < 10; i ++)
        for (int j = 0; j < 3; j ++)
            state_index[i][j] = -1;
    pw[0] = 1;
    for (int i = 1; i < 10; i ++)
        pw[i] = pw[i - 1] * 3;
    init_state();
    ///create_state(0, 7);
    /**for (int i = 0; i < strategy.size(); i ++, cout << endl)
    for (int j = 0; j <= N; j ++)
    cout << strategy[i][j] << " ";
    cout << endl;*/
    return strategy;
}

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