Submission #836563

#	Time	Username	Problem	Language	Result	Execution time	Memory
836563		SamAnd	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	10 ms	1108 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);
    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 * 3 + (x % 3);
    }
    for (int i = 1; i < sz(s); ++i)
    {
        if (((i - 1) / 3) % 2 == 1)
        {
            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;
                    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);
                }
            }
        }
    }
    return s;
}

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