Submission #1062128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062128		MarwenElarbi	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	34 ms	1148 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(23,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 = 1; i <= 22; ++i)
    {
        int k=7-(i-1)/3;
        tab[i][0]=(k%2 ? 1 : 0);
        int m=(i-1)%3;
        if(i==22) m++;
        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;
            }
            int nab=0;
            while(cnt>=pow(3,k)) cnt-=pow(3,k);
            if(cur>m) tab[i][j]=(k%2==1 ? -1 : -2);
            else if(cur<m) tab[i][j]=(k%2==1 ? -2 : -1);
            else if(k==0) tab[i][j]=22;
            else {
                if(cnt>=2*pow(3,k-1)) nab=2;
                else if(cnt>=pow(3,k-1)) nab=1;
                else nab=0;
                tab[i][j]=((i-1)/3+1)*3+nab+1;
                if(tab[i][j]==24) tab[i][j]=-1;
                else if(tab[i][j]==22) tab[i][j]=-2;
                else if(k==1) tab[i][j]=22;
            }
        }

    }
    return tab;
}

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