Submission #639723

#	Time	Username	Problem	Language	Result	Execution time	Memory
639723		huutuan	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	1 ms	212 KiB

prison

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

using namespace std;

vector<vector<int>> v;

void dnc(int id, int a, int L, int R, int l, int r){
    for (int i=l; i<=r; ++i) v[id][i]=a;
    for (int i=L; i<=l; ++i) v[a][i]=-1-v[a][0];
    for (int i=r; i<=R; ++i) v[a][i]=-2+v[a][0];
    ++l; --r;
    if (r<l) return;
    if (r-l<2){
        dnc(a, a+4, l-1, r+1, l, r);
        return;
    }
    if (r-l<4){
        dnc(a, a+4, l-1, r+1, l, (l+r)>>1);
        dnc(a, a+5, l-1, r+1, ((l+r)>>1)+1, r);
        return;
    }
    dnc(a, a+4, l-1, r+1, l, (l+l+r)/3);
    dnc(a, a+5, l-1, r+1, (l+l+r)/3+1, (l+r+r)/3);
    dnc(a, a+6, 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, 0, 1, N, 1, N);
    return v;
}

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