Submission #835319

#	Time	Username	Problem	Language	Result	Execution time	Memory
835319		SamAnd	Prisoner Challenge (IOI22_prison)	C++17	47 / 100	13 ms	1364 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;
const int m = 13;

std::vector<std::vector<int> > devise_strategy(int N)
{
    vector<vector<int> > s(1 + 8 * 4);
    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 + 7 * 4 + x % 3;
    }
    for (int i = 1; i < sz(s); ++i)
    {
        if ((i - 1) % 4 < 3)
        {
            s[i][0] = 1;
            for (int j = 1; j <= N; ++j)
            {
                int x = j;
                for (int k = 0; k < (i - 1) / 4; ++k)
                    x /= 3;
                if ((x % 3) > (i - 1) % 4)
                {
                    s[i][j] = -1;
                }
                else if ((x % 3) < (i - 1) % 4)
                {
                    s[i][j] = -2;
                }
                else
                {
                    s[i][j] = 1 + ((i - 1) / 4) * 4 + 3;
                }
            }
        }
        else
        {
            s[i][0] = 0;
            for (int j = 1; j <= N; ++j)
            {
                if ((i - 1) / 4 == 0)
                {
                    s[i][j] = 0;
                    continue;
                }
                int x = j;
                for (int k = 0; k < (i - 1) / 4 - 1; ++k)
                    x /= 3;
                s[i][j] = 1 + ((i - 1) / 4 - 1) * 4 + (x % 3);
            }
        }
    }
    return s;
}

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