Submission #697452

#	Time	Username	Problem	Language	Result	Execution time	Memory
697452		vjudge1	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	1428 KiB

prison

#include "prison.h"
#include <stdio.h>
#include <vector>
using namespace std;

vector<vector<int>> res;

void t(int cur, int l, int r, int total){
	if(l+1 >= r) return;
	for(int i=cur; i<=20; i++){
		res[i][l] = -1-res[i][0];
		res[i][r-1] = -2+res[i][0];
	}
	l++; r--;
	if(l == r) return;
	
	int k;
	if(total == 19) k = 2;
	else k = 3;
	
	for(int i=0; i<k; i++){
		int ll = ((k-i)*l+i*r)/k;
		int rr = ((k-i-1)*l+(i+1)*r)/k;
		for(int j=l; j<ll; j++){
			res[total+i][j] = -2+res[cur][0];
		}
		for(int j=ll; j<rr; j++){
			res[cur][j] = total+i;
		}
		for(int j=rr; j<r; j++){
			res[total+i][j] = -1-res[cur][0];
		}
		t(total+i, ll, rr, total+k);
	}
}

vector<vector<int>> devise_strategy(int N){
	res.resize(21, vector<int>(N+1, 0));
	res[0][0] = 0;
	for(int i=1; i<=20; i++){
		if((i-1)%6 < 3) res[i][0] = 1;
		else res[i][0] = 0;
	}
	t(0, 1, N+1, 1);
    return res;
}

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