Submission #634993

#	Time	Username	Problem	Language	Result	Execution time	Memory
634993		radal	Prisoner Challenge (IOI22_prison)	C++17	72 / 100	14 ms	1584 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2")
#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 5e5+20,mod = 1e9+7,inf = 1e9+10;

vector<vector<int> > ve;
int pw[10];
vector<vector<int>> devise_strategy(int n) {
    pw[0] = 1;
    rep(i,1,10) pw[i] = 3*pw[i-1];
    ve.resize(24);
    rep(i,0,24){
        ve[i].resize(n+1);
        if (!i){
            ve[i][0] = 0;
            ve[i][n] = -2;
            rep(j,1,n){
                if (j >= 2*pw[7]){
                    ve[i][j] = 23;
                    continue;
                }
                if (j >= pw[7]){
                    ve[i][j] = 22;
                    continue;
                }
                ve[i][j] = 21;
                continue;
            }
            continue;
        }
        int ch = i/3;
        bool f = ch%2;
        if (f){
            ve[i][0] = 1;
            ve[i][n] = -1;
            rep(j,1,n){
                if (i%3 == 2){
                    if (j%pw[ch+1] < 2*pw[ch]){
                        ve[i][j] = -2;
                        continue;
                    }
                }
                if (i%3 == 1){
                    if (j%pw[ch+1] < pw[ch]){
                        ve[i][j] = -2;
                        continue;
                    }
                    if (j%pw[ch+1] >= 2*pw[ch]){
                        ve[i][j] = -1;
                        continue;
                    }
                }
                if (i%3 == 0){
                    if (j%pw[ch+1] >= pw[ch]){
                        ve[i][j] = -1;
                        continue;
                    }
                }
                if (!ch) continue;
                if (j%pw[ch] >= 2*pw[ch-1]){
                    ve[i][j] = 3*ch-1;
                    continue;
                }
                if (j%pw[ch] >= pw[ch-1]){
                    ve[i][j] = 3*ch-2;
                    continue;
                }
                if (ch == 1){
                    ve[i][j] = -2;
                    continue;
                }
                ve[i][j] = 3*(ch-1);
            }
            continue;
        }
        else{
            ve[i][0] = 0;
            ve[i][n] = -2;
            rep(j,1,n){
                if (i%3 == 2){
                    if (j%pw[ch+1] < 2*pw[ch]){
                        ve[i][j] = -1;
                        continue;
                    }
                }
                if (i%3 == 1){
                    if (j%pw[ch+1] < pw[ch]){
                        ve[i][j] = -1;
                        continue;
                    }
                    if (j%pw[ch+1] >= 2*pw[ch]){
                        ve[i][j] = -2;
                        continue;
                    }
                }
                if (i%3 == 0){
                    if (j%pw[ch+1] >= pw[ch]){
                        ve[i][j] = -2;
                        continue;
                    }
                }
                if (!ch) continue;
                if (j%pw[ch] >= 2*pw[ch-1]){
                    ve[i][j] = 3*ch-1;
                    continue;
                }
                if (j%pw[ch] >= pw[ch-1]){
                    ve[i][j] = 3*ch-2;
                    continue;
                }
                if (ch == 1){
                    ve[i][j] = -1;
                    continue;
                }
                ve[i][j] = 3*(ch-1);
            }
            continue;
        }
    }
    return ve;
}

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