Submission #626275

#	Time	Username	Problem	Language	Result	Execution time	Memory
626275		mraron	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	0 ms	212 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) {
            s[i][0]=0;
            for(int j=1;j<=N;++j) {
                s[i][j]=(j&1?1:2);
            }
        }else {
            int bit=(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]=THIS;
                }else if(curr<have) {
                    s[i][j]=OTHER;
                }else {
                    int nxt=(j&(1<<(bit+1)))!=0;
                    //~ std::cerr<<bit+1<<"!!\n";
                    if(bit+1==12) {
                        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*(bit+1)+1+nxt);
                        s[i][j]=2*(bit+1)+1+nxt;
                    }
                }
            }
        }
    }
    return s;
}
//~ 0 -> 1 2
//~ 1 -> 3 4
//~ 2 -> 5 6

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