Submission #837699

#	Time	Username	Problem	Language	Result	Execution time	Memory
837699		JakobZorz	Prisoner Challenge (IOI22_prison)	C++17	53 / 100	11 ms	1748 KiB

prison

#include"prison.h"
#include<vector>
using namespace std;

vector<vector<int>>strats;
int n;

int to_neg(int bag){
    return -1-bag;
}

int dp[20][2][2];
bool dpt[20][2][2];
int get_strat(int bit,int prev_bit,int prev_bag){
    if(dpt[bit][prev_bit][prev_bag])
        return dp[bit][prev_bit][prev_bag];
    
    int curr_strat=(int)strats.size();
    strats.push_back(vector<int>(n+1));
    int inspected_bag=prev_bag^1;
    strats[curr_strat][0]=inspected_bag;
    
    if(bit==0){
        for(int i=1;i<=n;i++){
            if(i%2==1){
                strats[curr_strat][i]=to_neg(prev_bag);
            }else{
                strats[curr_strat][i]=to_neg(inspected_bag);
            }
        }
        
        return curr_strat;
    }
    
    int strat0=get_strat(bit-1,0,prev_bag^1);
    int strat1=get_strat(bit-1,1,prev_bag^1);
    
    for(int i=1;i<=n;i++){
        bool curr_bit=(i&(1<<bit))!=0;
        if(curr_bit!=prev_bit){
            if(curr_bit){
                strats[curr_strat][i]=to_neg(prev_bag);
            }else{
                strats[curr_strat][i]=to_neg(inspected_bag);
            }
        }else{
            bool next_bit=(i&(1<<(bit-1)))!=0;
            if(next_bit==0){
                strats[curr_strat][i]=strat0;
            }else{
                strats[curr_strat][i]=strat1;
            }
        }
    }
    
    dpt[bit][prev_bit][prev_bag]=true;
    dp[bit][prev_bit][prev_bag]=curr_strat;
    
    return curr_strat;
}

vector<vector<int>>devise_strategy(int N){
    strats.clear();
    n=N;
    strats.push_back(vector<int>(n+1));
    
    int strat0=get_strat(12,0,0);
    int strat1=get_strat(12,1,0);
    
    for(int i=1;i<=n;i++){
        if(i&(1<<12)){
            strats[0][i]=strat1;
        }else{
            strats[0][i]=strat0;
        }
    }
    return strats;
}

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