제출 #837627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
837627		JakobZorz	죄수들의 도전 (IOI22_prison)	C++17	0 / 100	4 ms	3852 KiB

prison

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

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

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

int get_strat(int bit,int prev_bit,int 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(inspected_bag);
            }else{
                strats[curr_strat][i]=to_neg(prev_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(inspected_bag);
            }else{
                strats[curr_strat][i]=to_neg(prev_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;
            }
        }
    }
    
    return curr_strat;
}

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

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