Submission #1039408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039408		Marco_Escandon	Prisoner Challenge (IOI22_prison)	C++17	50 / 100	14 ms	1372 KiB

prison

using namespace std;
#pragma once
 
const int BL = 5;
 
int digit(int x, int y){
    while(y--){
        x/=BL;
    }
    return x%BL;
}
 
#include <vector>
std::vector<std::vector<int>> devise_strategy(int n)
{
    int L = 0;
    int sz = 1;
    {
        int cn = n;
        while(cn){
            L++;
            sz+=BL;
            cn/=BL;
        }
    }
    vector<vector<int>> s(sz,vector<int>(n+1,0));
    s[0][0]=L%2;
    for(int i=1; i<=n; i++){
        s[0][i]=1+digit(i, L-1);
    }
    for(int i=1; i<sz; i++){
        int bit = L - 1 - ((i-1)/BL);
//        cout << bit << " ";
        int prev = (i-1)%BL;
        s[i][0]=bit%2;
        int next_hop = i+BL-prev;
        for(int j=1; j<=n; j++){
            int d = digit(j, bit);
            if(bit==0){
                if(d<prev) {
                    s[i][j]=-(1+s[i][0]);
                }
                if(d>prev) {
                    s[i][j]=-(2-s[i][0]);
                }
            }
            else if (bit==1&&d==prev) {
                int d1 = digit(j, bit-1);
                if(d1==0) {
                    s[i][j]=-(1+s[i][0]);
                }
                else if(d1==BL-1) {
                    s[i][j]=-(2-s[i][0]);
                }
                else {
                    s[i][j]=next_hop+d1;
                }
            }
            else {
                if(d==prev) {
                    s[i][j]=next_hop+digit(j, bit-1);
                }
                if(d<prev) {
                    s[i][j]=-(1+s[i][0]);
                }
                if(d>prev) {
                    s[i][j]=-(2-s[i][0]);
                }
            }
        }
    }
    return s;
}

Compilation message (stderr)

prison.cpp:2:9: warning: #pragma once in main file
    2 | #pragma once
      |         ^~~~

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