Submission #625546

#	Time	Username	Problem	Language	Result	Execution time	Memory
625546		jeroenodb	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	13 ms	1072 KiB

prison

#include "prison.h"
#include <array>
#include <vector>
using namespace std;
const int D = 11;
std::vector<std::vector<int>> devise_strategy(int N) {
    array<int,D> dig = {2,2,2,2,2,2,3,3,3,3,1};
    array<int,D> pw = {1};
    for(int i=1;i<D;++i) pw[i]=pw[i-1]*dig[i-1];
    auto extractDig = [&](int n, int i) {
       n/=pw[i];
       return n%dig[i];
    };
    auto endResult = [&](int dif, int f) {
        if(f==0) dif=-dif;
        if(dif<=0) return -2;
        else return -1;
    };
    vector<vector<int>> res;
    
    for(int i=D-1;i>=1;--i) {
        // if(pw[i]>=N) continue;
        int at = res.size();
        // before
        vector<int> cur(N+1);
        for(int d=0;d<dig[i];++d) {
            cur[0]=i&1;
            for(int b=0;b<N;++b) {
                if(extractDig(b,i)!=d) {
                    cur[b+1] = endResult(extractDig(b,i)-d, cur[0]);
                } else if(i==1) {
                    cur[b+1] = endResult((b&1)*2-1,cur[0]);
                } else {
                    cur[b+1] = at+dig[i]+extractDig(b,i-1);
                }
            }
            res.push_back(cur);
        }
    }
    return res;
    
}

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