Submission #888197

#	Time	Username	Problem	Language	Result	Execution time	Memory
888197		abcvuitunggio	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	16 ms	1372 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=21;
vector <vector <int>> res(sz);
void f(int l, int r, int st, int i, int b){
    if (l>r)
        return;
    res[i][0]=b;
    res[i][l]=-1-b;
    res[i][r]=b-2;
    if (l+1>r-1)
        return;
    int x=2+(r-l>4),d=(r-l+1)/x;
    for (int j=l+1;j<=l+d;j++){
        res[i][j]=st;
        res[st][l]=b-2;
        for (int k=l+d+1;k<=r;k++)
            res[st][k]=-1-b;
    }
    for (int j=l+d+1;j<=min(l+d*2,r-1);j++){
        res[i][j]=st+1;
        for (int k=l;k<=l+d;k++)
            res[st+1][k]=b-2;
        for (int k=min(l+d*2,r-1)+1;k<=r;k++)
            res[st+1][k]=-1-b;
    }
    for (int j=min(l+d*2,r-1)+1;j<r;j++){
        res[i][j]=st+2;
        for (int k=l;k<=min(l+d*2,r-1);k++)
            res[st+2][k]=b-2;
        res[st+2][r]=-1-b;
    }
    f(l+1,l+d,st+x,st,b^1);
    f(l+d+1,min(l+d*2,r-1),st+x,st+1,b^1);
    f(min(l+d*2,r-1)+1,r-1,st+x,st+2,b^1);
}
vector <vector <int>> devise_strategy(int n){
    for (int i=0;i<sz;i++)
        res[i]=vector <int> (n+1,0);
    f(1,n,1,0,0);
    return res;
}

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