제출 #633482

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
633482		Lawliet	죄수들의 도전 (IOI22_prison)	C++17	53 / 100	31 ms	1204 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 < 6 ; 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*6;
    v.push_back( vector<int>(n + 1, 0) );

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

        if( j%9 == 0 )
            v[root][j] = -1;
        else if( j%9 == 8 )
            v[root][j] = -2;
        else
            v[root][j] = root + 1;
    }

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

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

        if( j%9 <= 1 )
            v[root][j] = -2;
        else if( j%9 >= 7 )
            v[root][j] = -1;
        else
            v[root][j] = root + 1;
    }

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

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

        if( j%9 <= 2 )
            v[root][j] = -1;
        else if( j%9 >= 6 )
            v[root][j] = -2;
        else
            v[root][j] = root + 1;
    }

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

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

        if( j%9 <= 3 )
            v[root][j] = -2;
        else if( j%9 >= 5 )
            v[root][j] = -1;
        else
            v[root][j] = root + 1;
    }

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

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

        if( j%9 <= 4 )
            v[root][j] = -1;
        else if( j%9 >= 5 )
            v[root][j] = -2;
    }

    return v;
}

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