Submission #626286

#	Time	Username	Problem	Language	Result	Execution time	Memory
626286		mraron	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	17 ms	1064 KiB

prison

#include "prison.h"

#include <vector>
#include <iostream>
#include <cassert>

std::vector<std::vector<int>> devise_strategy(int N) {
    int x=24;
    std::vector<std::vector<int>> s(x+1, std::vector<int>(N+1, 0));
    for(int i=0;i<=x;++i) {
        if(i==0) {
            int bit=12;
            s[i][0]=0;
            for(int j=1;j<=N;++j) {
                s[i][j]=(j&(1<<bit)?1:2);
            }
        }else {
            int bit=12-(i-1)/2;
            int bag=(bit&1)^1;
            //~ std::cerr<<i<<" -> "<<bag<<"\n";
            int have=(i&1?1:0);
            s[i][0]=bag;
            int THIS=bag==0?-1:-2;
            int OTHER=bag==0?-2:-1;
            for(int j=1;j<=N;++j) {
                int curr=(j&(1<<bit))!=0;
                if(curr>have) {
                    s[i][j]=OTHER;
                }else if(curr<have) {
                    s[i][j]=THIS;
                }else {
                    int nxt=(j&(1<<(bit-1)))!=0;
                    //~ std::cerr<<bit+1<<"!!\n";
                    if(bit-1==0) {
                        if(nxt==0) {
                            s[i][j]=THIS;
                        }else {
                            s[i][j]=OTHER;
                        }
                    }else {
                        //~ std::cerr<<i<<" "<<2*(bit+1)+1+nxt<<"\n";
                        assert(i!=2*(12-bit+1)+1+nxt);
                        s[i][j]=2*(12-bit+1)+2-nxt;
                    }
                }
            }
        }
    }
    return s;
}
//~ 0 -> 1 2
//~ 1 -> 3 4
//~ 2 -> 5 6

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