Submission #1055575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055575		vjudge1	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	6 ms	1116 KiB

prison

#include "prison.h"

#include <vector>
using namespace std;
int ithidk(int n,int ind){
    while(ind--)
        n/=3;
    return n%3;
}
int pw[10];
int lstidk(int n,int ind){
    return n % pw[ind];
}
vector<int> which_to_do(int num,int n){
    vector<int>res(n+1);
    res[0]=(num+2)/3&1;
    int BBit=8-(num+2)/3,vl=(num-1)%3;
    if(!num)
        for(int i=1;i<=n;i++)
            res[i]=ithidk(i,7)+1;
    else for(int i=1;i<=n;i++) {
            int c=ithidk(i,BBit);
            if(c<vl)res[i]=-res[0]-1;
            else if(c>vl)res[i]=-!res[0]-1;
            else { int K=lstidk(i,BBit);
                if(K==0) res[i]=-res[0]-1;
                else if(K==pw[BBit]-1)
                    res[i]=-!res[0]-1;
                else res[i]=min(22,ithidk(i,BBit-1)+1+(num+2)/3*3);
            }
        }
    return res;
}
vector<int>finale(int n){
    vector<int>res(n+1);
    for(int i=1;i<=n;i++)
        res[i]=(i%3?-2:-1);
    return res;
}
vector<vector<int>> devise_strategy(int N) {
    pw[0]=1;
    for(int i=1;i<10;i++)
        pw[i]=pw[i-1]*3;
    vector<vector<int>> ans;
    for(int i=0;i<22;i++)
        ans.push_back(which_to_do(i,N));
    ans.push_back(finale(N));
    return ans;
}

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