Submission #638579

#	Time	Username	Problem	Language	Result	Execution time	Memory
638579		pigeonbat	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	14 ms	1620 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
int group[5010][10];

void f(int s,int e,int d){
    if(s>e) return;
    group[s][d]=-1;
    group[e][d]=-2;
    if(e-s<2) return;
    if(d==6){
        int k=(e-s-1)/2;
        for(int i=0;i<k;i++) group[s+1+i][d]=d*3+1;
        for(int i=k;i<2*k;i++) group[s+1+i][d]=d*3+2;
        if((e-s-1)%2==1) group[e-1][d]=d*3+2;
        f(s+1,s+k,d+1); f(s+k+1,e-1,d+1);
        return;
    }
    int k=(e-s-1)/3;
    if((e-s-1)%3 == 0){
        for(int i=0;i<k;i++) group[s+1+i][d]=d*3+1;
        for(int i=k;i<2*k;i++) group[s+1+i][d]=d*3+2;
        for(int i=2*k;i<3*k;i++) group[s+1+i][d]=d*3+3;
        f(s+1,s+k,d+1); f(s+k+1,s+2*k,d+1); f(s+2*k+1,s+3*k,d+1);
    }
    else if((e-s-1)%3 == 1){
        for(int i=0;i<k;i++) group[s+1+i][d]=d*3+1;
        for(int i=k;i<2*k;i++) group[s+1+i][d]=d*3+2;
        for(int i=2*k;i<3*k+1;i++) group[s+1+i][d]=d*3+3;
        f(s+1,s+k,d+1); f(s+k+1,s+2*k,d+1); f(s+2*k+1,s+3*k+1,d+1);
    }
    else{
        for(int i=0;i<k;i++) group[s+1+i][d]=d*3+1;
        for(int i=k;i<2*k+1;i++) group[s+1+i][d]=d*3+2;
        for(int i=2*k+1;i<3*k+2;i++) group[s+1+i][d]=d*3+3;
        f(s+1,s+k,d+1); f(s+k+1,s+2*k+1,d+1); f(s+2*k+2,s+3*k+2,d+1);
    }
}

vector<vector<int>> re;

std::vector<std::vector<int>> devise_strategy(int N) {
    f(1, N, 0);
//    for(int t=0;t<7;t++){
//        for(int i=1;i<=N;i++) printf("%2d ",group[i][t]);
//        printf("\n");
//    }
    vector<int> tmp; tmp.push_back(0);
    for(int i=1;i<=N;i++) tmp.push_back(group[i][0]);
//    printf("\n");
//    for(int i=0;i<=N;i++) printf("%2d ",tmp[i]);
//    printf("\n");
    re.push_back(tmp);
    for(int t=1;t<=20;t++){
        tmp.clear(); tmp.resize(0);
        int tp = ((t-1)/3+1)%2;
        tmp.push_back(tp);
        for(int i=1;i<=N;i++){
            if(group[i][(t-1)/3]==-1) tmp.push_back(tp?-2:-1);
            else if(group[i][(t-1)/3]==-2) tmp.push_back(tp?-1:-2);
            else if(group[i][(t-1)/3]<t) tmp.push_back(tp?-2:-1);
            else if(group[i][(t-1)/3]>t) tmp.push_back(tp?-1:-2);
            else if(group[i][(t-1)/3+1]==-1) tmp.push_back(tp?-2:-1);
            else if(group[i][(t-1)/3+1]==-2) tmp.push_back(tp?-1:-2);
            else tmp.push_back(group[i][(t-1)/3+1]);
        }
//        for(int i=0;i<=N;i++) printf("%2d ",tmp[i]);
//        printf("\n");
        re.push_back(tmp);
    }
    return re;
}

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