Submission #633453

#	Time	Username	Problem	Language	Result	Execution time	Memory
633453		Lawliet	Prisoner Challenge (IOI22_prison)	C++17	51.50 / 100	34 ms	1292 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> decompose(int x)
{
    vector<int> digits;

    for(int i = 0 ; i < 8 ; i++, x /= 3)
        digits.push_back( x%3 );

    reverse( digits.begin() , digits.end() );

    return digits;
}

vector<vector<int>> devise_strategy(int N) 
{
    int n = N;
    vector< vector<int> > v;

    for(int i = 0 ; i < 7 ; i++)
    {
        int root = 4*i;
        v.push_back( vector<int>(n + 1, 0) );

        for(int j = 1 ; j <= n ; j++)
        {
            vector<int> d = decompose(j);
            v[root][j] = root + d[i] + 1;
        }

        v.push_back( vector<int>(n + 1, 1) ); // r = 0

        for(int j = 1 ; j <= n ; j++)
        {
            vector<int> d = decompose(j);

            if( d[i] == 0 )
                v[root + 1][j] = root + 4;
            else
                v[root + 1][j] = -1;
        }

        v.push_back( vector<int>(n + 1, 1) ); // r = 1

        for(int j = 1 ; j <= n ; j++)
        {
            vector<int> d = decompose(j);

            if( d[i] == 0 )
                v[root + 2][j] = -2;
            else if( d[i] == 1 )
                v[root + 2][j] = root + 4;
            else
                v[root + 2][j] = -1;
        }

        v.push_back( vector<int>(n + 1, 1) ); // r = 2

        for(int j = 1 ; j <= n ; j++)
        {
            vector<int> d = decompose(j);

            if( d[i] == 2 )
                v[root + 3][j] = root + 4;
            else
                v[root + 3][j] = -2;
        }
    }

    int root = 4*7;
    v.push_back( vector<int>(n + 1, 0) );

    for(int j = 1 ; j <= n ; j++)
    {
        vector<int> d = decompose(j);

        if( d[7] == 0 )
            v[root][j] = -1;
        else if( d[7] == 1 )
            v[root][j] = root + 1;
        else
            v[root][j] = -2;
    }

    root++;
    v.push_back( vector<int>(n + 1, 1) );

    for(int j = 1 ; j <= n ; j++)
    {
        vector<int> d = decompose(j);

        if( d[7] == 0 )
            v[root][j] = -2;
        else if( d[7] == 1 )
            v[root][j] = -1;
        else
            v[root][j] = -1;
    }

    return v;
}

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