Submission #639720

#	Time	Username	Problem	Language	Result	Execution time	Memory
639720		huutuan	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	1404 KiB

prison

#include "prison.h"
#include<bits/stdc++.h>

using namespace std;

vector<vector<int>> v;

void dnc(int id, int a, int b, int L, int R, int l, int r){
    for (int i=l; i<=r; ++i) v[id][i]=a*3+b;
    for (int i=L; i<=l; ++i) v[a*3+b][i]=-1-v[a*3+b][0];
    for (int i=r; i<=R; ++i) v[a*3+b][i]=-2+v[a*3+b][0];
    ++l; --r;
    if (r<l) return;
    if (r-l<2){
        dnc(a*3+b, a+1, 1, l-1, r+1, l, r);
        return;
    }
    if (r-l<4){
        dnc(a*3+b, a+1, 1, l-1, r+1, l, (l+r)>>1);
        dnc(a*3+b, a+1, 2, l-1, r+1, ((l+r)>>1)+1, r);
        return;
    }
    dnc(a*3+b, a+1, 1, l-1, r+1, l, (l+l+r)/3);
    dnc(a*3+b, a+1, 2, l-1, r+1, (l+l+r)/3+1, (l+r+r)/3);
    dnc(a*3+b, a+1, 3, l-1, r+1, (l+r+r)/3+1, r);
}

vector<vector<int>> devise_strategy(int N){
    vector<vector<int>>(21, vector<int>(N+1)).swap(v);
    for (int i=0; i<21; ++i) if ((i+2)%6<3) ++v[i][0];
    dnc(0, -1, 3, 1, N, 1, N);
    return v;
}

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