Submission #635794

#	Time	Username	Problem	Language	Result	Execution time	Memory
635794		huutuan	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	5 ms	560 KiB

prison

#include "prison.h"
#include<bits/stdc++.h>

using namespace std;

int encode(pair<int, int> x){
    if (x.first<4) return x.first*2+x.second+1;
    return (x.first-1)*3+x.second;
}

pair<int, int> decode(int x){
    if (x<9) return {(x-1)/2, (x-1)%2};
    return {x/3+1, x%3};
}

int p[]={1, 3, 9, 27, 81, 243, 729, 2187, 6561};

int getbit3(int i, int j){
    i-=2;
    return j%p[8-i]/p[8-i-1];
}

int getbit2(int i, int j){
    return (j>>(12ll-i))&1ll;
}

vector<vector<int>> devise_strategy(int n){
    vector<vector<int>> v(21, vector<int>(n+1));
    for (int j=1; j<=n; ++j) v[0][j]=encode({0, getbit2(0, j)});
    for (int i=1; i<18; ++i){
        auto p=decode(i);
        v[i][0]=!(p.first&1ll);
        for (int j=1; j<=n; ++j){
            int t=(i<9)?getbit2(p.first, j):getbit3(p.first, j);
            if (p.second<t) v[i][j]=v[i][0]-2;
            else if (p.second>t) v[i][j]=(!v[i][0])-2;
            else{
                if (i>14){
                    int r=j%9;
                    if (r==0) v[i][j]=-2;
                    else if (r==8) v[i][j]=-1;
                    else if (r<=4) v[i][j]=18;
                    else v[i][j]=19;
                }
                else v[i][j]=encode({p.first+1, (p.first+1<4)?getbit2(p.first+1, j):getbit3(p.first+1, j)});
            }
        }
    }
    for (int i=18; i<20; ++i){
        for (int j=1; j<=n; ++j){
            int t=j%9;
            if (t==0) v[i][j]=-1;
            else if (t==8) v[i][j]=-2;
            else if (i==18){
                if (t==1) v[i][j]=-1;
                else if (t>=4) v[i][j]=-2;
                else v[i][j]=20;
            }else{
                if (t<=5) v[i][j]=-1;
                else if (t==7) v[i][j]=-2;
                else v[i][j]=20;
            }
        }
    }
    v[20][0]=1;
    for (int j=1; j<=n; ++j){
        int r=j%9;
        if (r<=4){
            if (r<=2) v[20][j]=-2;
            else v[20][j]=-1;
        }else{
            if (r<=6) v[20][j]=-2;
            else v[20][j]=-1;
        }
    }
    return v;
}

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