Submission #859242

#	Time	Username	Problem	Language	Result	Execution time	Memory
859242		12345678	Prisoner Challenge (IOI22_prison)	C++17	72 / 100	11 ms	1884 KiB

prison

#include "prison.h"
 
#include <bits/stdc++.h>
 
using namespace std;
 
const int nx=6561, kx=24;
int p[11];
vector<vector<int>> ans(kx+1, vector<int> (nx+1));
 
std::vector<std::vector<int>> devise_strategy(int N) {
    for (int i=1; i<=nx; i++) ans[0][i]=(i-1)/2187+1;
    p[0]=1;
    for (int i=1; i<11; i++) p[i]=p[i-1]*3;
    for (int i=1; i<=kx; i++)
    {
        int col=(i-1)/3+1, pw=p[8-col], pv=(i-1)%3;
        bool isa=col%2;
        ans[i][0]=(int)isa;
        
        for (int j=1; j<=nx; j++)
        {
            int rem=((j-1)%p[8-col+1])/pw;
            if (rem!=pv)
            {
                if ((rem>pv&&isa)||(rem<pv&&!isa)) ans[i][j]=-1;
                if ((rem>pv&&!isa)||(rem<pv&&isa)) ans[i][j]=-2;
            }
            else
            {
                if (3*col==kx) continue;
                int np=p[8-col-1], nw=(j-1)%p[8-col];
                ans[i][j]=nw/np+1+3*col;
                if (ans[i][j]==24) ans[i][j]=-1;
            }
            //if (i==24&&ans[i][j]!=-2&&ans[i][j]!=0) cout<<"here"<<' '<<j<<' '<<ans[i][j]<<'\n';
        }
        //cout<<i<<' '<<col<<' '<<isa<<' '<<pw<<' '<<pv<<'\n';
    }
    vector<vector<int>> ans2(24, vector<int> (N+1));
    for (int i=0; i<=23; i++) for (int j=0; j<=N; j++) ans2[i][j]=ans[i][j];
    return ans2;
}

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