Submission #859252

#	Time	Username	Problem	Language	Result	Execution time	Memory
859252		12345678	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	11 ms	1864 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 (ans[i][j]==22) ans[i][j]=-2;
                if (ans[i][j]==23) ans[i][j]=22;
            }
            //if (i==22&&ans[i][j]!=-2&&ans[i][j]!=0) cout<<"here"<<' '<<j<<' '<<ans[i][j]<<'\n';
        }
    }
    vector<vector<int>> ans2(23, vector<int> (N+1));
    for (int i=0; i<=21; i++) for (int j=0; j<=N; j++) ans2[i][j]=ans[i][j];
    for (int i=0; i<=N; i++) ans2[22][i]=ans[23][i]; 
    return ans2;
}

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