Submission #888193

#	Time	Username	Problem	Language	Result	Execution time	Memory
888193		abcvuitunggio	Prisoner Challenge (IOI22_prison)	C++17	10 / 100	5 ms	1116 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector <vector <int>> res(21);
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>3),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){
    n=N;
    for (int i=0;i<21;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: 0 / 90