Submission #1061556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061556		MarwenElarbi	Prisoner Challenge (IOI22_prison)	C++17	48.50 / 100	34 ms	1364 KiB

prison

#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
#define pb push_back
#define ll long long
#define fi first
#define se second

std::vector<std::vector<int>> devise_strategy(int N) {
    vector<vector<int>> tab(32,vector<int> (N+1,0));
    int n=N;
    tab[0][0]=0;
    for (int i = 1; i < n+1; ++i)
    {
        if(i>=2*pow(3,7)){
            tab[0][i]=3;
        }else if(i>=pow(3,7)){
            tab[0][i]=2;
        }else{
            tab[0][i]=1;
        }
    }
    for (int i = 25; i <= 31; ++i)
    {
        tab[i][0]=0;
    }
    for (int j = 1; j < n+1; ++j)
    {
        int cnt=j;
        while(cnt>=pow(3,7)) cnt-=pow(3,7);
        for (int k = 6; k >= 0; k--)
        {
            if(cnt>=2*pow(3,k)){
                tab[31-k][j]=3+(7-k)*3;
            }else if(cnt>=pow(3,k)){
                tab[31-k][j]=2+(7-k)*3;
            }else{
                tab[31-k][j]=1+(7-k)*3;
            }
            while(cnt>=pow(3,k)) cnt-=pow(3,k);
        }
    }
    for (int i = 1; i <= 24; ++i)
    {
        tab[i][0]=1;
        int k=7-(i-1)/3;
        int m=(i-1)%3;
        for (int j = 1; j < n+1; ++j)
        {
            int cnt=j;
            for (int t = 7; t > k; --t)
            {
                while(cnt>=pow(3,t)) cnt-=pow(3,t);
            }
            int cur;
            if(cnt>=2*pow(3,k)){
                cur=2;
            }else if(cnt>=pow(3,k)){
                cur=1;
            }else{
                cur=0;
            }
            if(cur>m) tab[i][j]=-1;
            else if(cur<m) tab[i][j]=-2;
            else tab[i][j]=min(31,31-(k-1));
        }

    }
    return tab;
}

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