Submission #635650

#	Time	Username	Problem	Language	Result	Execution time	Memory
635650		huutuan	Prisoner Challenge (IOI22_prison)	C++17	72 / 100	17 ms	1108 KiB

prison

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

using namespace std;

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

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

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

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

vector<vector<int>> devise_strategy(int n){
    vector<vector<int>> v(24, vector<int>(n+1));
    for (int j=1; j<=n; ++j) v[0][j]=encode({0, getbit(0, j)});
    for (int i=1; i<22; ++i){
        auto p=decode(i);
        v[i][0]=!(p.first&1ll);
        for (int j=1; j<=n; ++j){
            int t=getbit(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>18){
                    int t=getbit(p.first+1, j);
                    if (t==0) v[i][j]=-2;
                    if (t==2) v[i][j]=-1;
                    if (t==1) v[i][j]=22;
                }
                else v[i][j]=encode({p.first+1, getbit(p.first+1, j)});
            }
        }
    }
    v[22][0]=0;
    for (int j=1; j<=n; ++j){
        int t=getbit(7, j);
        if (t==0) v[22][j]=-1;
        else v[22][j]=-2;
    }
    return v;
}

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