Submission #836579

#	Time	Username	Problem	Language	Result	Execution time	Memory
836579		SamAnd	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	12 ms	1016 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;

std::vector<std::vector<int> > devise_strategy(int N)
{
    vector<vector<int> > s(1 + 8 * 3 - 2);
    for (int i = 0; i < sz(s); ++i)
        s[i].assign(N + 1, -3);

    s[0][0] = 0;
    for (int j = 1; j <= N; ++j)
    {
        int x = j;
        for (int k = 0; k < 7; ++k)
            x /= 3;
        s[0][j] = 1 + 6 * 3 + (x % 3);
    }
    for (int i = 1; i < sz(s) - 1; ++i)
    {
        if (((i - 1) / 3) % 2 == 0)
        {
            s[i][0] = 1;
            for (int j = 1; j <= N; ++j)
            {
                int x = j;
                for (int k = 0; k <= (i - 1) / 3; ++k)
                    x /= 3;
                if ((x % 3) > (i - 1) % 3)
                {
                    s[i][j] = -1;
                }
                else if ((x % 3) < (i - 1) % 3)
                {
                    s[i][j] = -2;
                }
                else
                {
                    int x = j;
                    for (int k = 0; k <= (i - 1) / 3 - 1; ++k)
                        x /= 3;
                    if ((i - 1) / 3 == 0)
                    {
                        if ((x % 3) == 0)
                            s[i][j] = -2;
                        else if ((x % 3) == 2)
                            s[i][j] = -1;
                        else
                            s[i][j] = 22;
                    }
                    else
                        s[i][j] = 1 + ((i - 1) / 3 - 1) * 3 + (x % 3);
                }
            }
        }
        else
        {
            s[i][0] = 0;
            for (int j = 1; j <= N; ++j)
            {
                int x = j;
                for (int k = 0; k <= (i - 1) / 3; ++k)
                    x /= 3;
                if ((x % 3) > (i - 1) % 3)
                {
                    s[i][j] = -2;
                }
                else if ((x % 3) < (i - 1) % 3)
                {
                    s[i][j] = -1;
                }
                else
                {
                    int x = j;
                    for (int k = 0; k <= (i - 1) / 3 - 1; ++k)
                        x /= 3;
                    s[i][j] = 1 + ((i - 1) / 3 - 1) * 3 + (x % 3);
                }
            }
        }
    }
    s[22][0] = 0;
    for (int j = 1; j <= N; ++j)
    {
        if ((j % 3) == 0)
            s[22][j] = -1;
        else if ((j % 3) == 2)
            s[22][j] = -2;
        else
            s[22][j] = 0;
    }
    return s;
}

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