Submission #631020

#	Time	Username	Problem	Language	Result	Execution time	Memory
631020		k_balint31415	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	13 ms	2004 KiB

prison

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> t(23,vector<int>(5001));
vector<int> szam[5001];
vector<int> ert;

void f(int k){
    for(int i=1;i<ert.size();i++){
        szam[k].push_back(k%ert[i-1]/ert[i]);
    }
}

int mp[23][2]{
    {0,0},
    {0,0},{0,1},{0,2},
    {1,0},{1,1},{1,2},
    {2,0},{2,1},{2,2},
    {3,0},{3,1},{3,2},
    {4,0},{4,1},
    {5,0},{5,1},
    {6,0},{6,1},
    {7,0},{7,1},
    {8,0},{8,1}
};

int rmp[9][3]{
    {1,2,3},
    {4,5,6},
    {7,8,9},
    {10,11,12},
    {13,14,0},
    {15,16,0},
    {17,18,0},
    {19,20,0},
    {21,22,0}
};

vector<vector<int>> devise_strategy(int N){
    ert.push_back(1);
    for(int i=1;i<=6;i++) ert.push_back(2*ert.back());
    for(int i=1;i<=4;i++) ert.push_back(3*ert.back());
    reverse(ert.begin(),ert.end());
    for(int i=1;i<=5000;i++) f(i);

    t[0][0]=0;
    for(int i=1;i<=5000;i++){
        t[0][i]=rmp[0][szam[i][0]];
    }

    for(int i=1;i<=22;i++){
        t[i][0]=mp[i][0]&1^1;
        for(int j=1;j<=5000;j++){
            if(szam[j][mp[i][0]]<mp[i][1]){
                if(t[i][0]==0) t[i][j]=-1;
                else t[i][j]=-2;
            }
            else if(szam[j][mp[i][0]]>mp[i][1]){
                if(t[i][0]==0) t[i][j]=-2;
                else t[i][j]=-1;
            }
            else{
                if(i==21 || i==22){
                    if(szam[j][9]==0) t[i][j]=-2;
                    else t[i][j]=-1;
                }
                else{
                    t[i][j]=rmp[mp[i][0]+1][szam[j][mp[i][0]+1]];
                }
            }
        }
    }

    for(int i=0;i<=22;i++){
        t[i].resize(N+1);
    }

    return t;
}

Compilation message (stderr)

prison.cpp: In function 'void f(int)':
prison.cpp:9:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for(int i=1;i<ert.size();i++){
      |                 ~^~~~~~~~~~~
prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:52:25: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   52 |         t[i][0]=mp[i][0]&1^1;
      |                 ~~~~~~~~^~

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