Submission #626485

#	Time	Username	Problem	Language	Result	Execution time	Memory
626485		mraron	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	27 ms	1008 KiB

prison

#include "prison.h"

#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
using namespace std;

const int BASE=3;
const int START=7;
    
int get_bit(int x, int bit, int base=2) {
    vector<int> lst;
    while(x>0) {
        lst.push_back(x%base);
        x/=base;
    }
    
    return (bit>=(int)lst.size()?0:lst[bit]);
}

std::vector<std::vector<int>> devise_strategy(int N) {
    //~ cerr<<get_bit(2187, 7, 3)<<"\n";
    //~ cerr<<get_bit(2181, 7, 3)<<"\n";
    //~ exit(0);
    //~ std::cerr<<get_bit(2, START, BASE)<<"\n";
    int x=22;
    std::vector<std::vector<int>> s(x+1, std::vector<int>(N+1, 0));
    //~ cerr<<"digraph G {\n";
    for(int i=0;i<=x;++i) {
        if(i==0) {
            s[i][0]=0;
            for(int j=1;j<=N;++j) {
                s[i][j]=1+get_bit(j, START, BASE);
                //~ cerr<<i<<" -> "<<s[i][j]<<"\n";
            }
        }else {
            int bit=START-(i-1)/BASE;
            int bag=(((i-1)/BASE)&1)^1;
            
            int have=(i-1)%BASE;
            if(i==x) have++; //mod3
            s[i][0]=bag;
            int THIS=bag==0?-1:-2;
            int OTHER=bag==0?-2:-1;
            //~ if(i==1) cerr<<have<<"\n";
            for(int j=1;j<=N;++j) {
                int curr=get_bit(j,bit, BASE);
                //~ if(j==2187) cerr<<i<<" "<<have<<" "<<curr<<"???\n";
                //~ if(i==1) cerr<<curr<<"\n";
                if(curr>have) {
                    s[i][j]=OTHER;
                }else if(curr<have) {
                    s[i][j]=THIS;
                }else {
                    int nxt=get_bit(j, bit-1, BASE);
                    if(bit-1==0) {
                        if(nxt==0) {
                            s[i][j]=THIS;
                        }else if(nxt==2) {
                            s[i][j]=OTHER;
                        }else {
                            s[i][j]=22;
                        }
                    }else {
                        
                        s[i][j]=BASE*(START-bit+1)+1+nxt;
                        if(i==22)  s[i][j]=THIS;
                    }
                }
            }
        }
    }
    //~ cerr<<s[0][2181]<<"\n";
    //~ cerr<<s[0][0]<<"\n";
    //~ cerr<<s[s[0][2181]][0]<<"\n";
    //~ cerr<<s[s[0][2181]][2187]<<"\n";
    //~ for(auto i:s) {
    //~ for(auto j:i) cerr<<j<<" ";
    //~ cerr<<"\n";
    //~ }
    //~ cerr<<"}\n";
    return s;
}
    

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