Submission #639770

#	Time	Username	Problem	Language	Result	Execution time	Memory
639770		study	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	11 ms	1364 KiB

prison

#include <bits/stdc++.h>
#include "prison.h"
using namespace std;

vector<vector<int>> ans;

void calc(int prev, int level, int where, int prev_l, int prev_r, int L, int R, int iter){
	int idx = (level-1)*3+where;
	if (iter%2 == 0) ans[idx][0] = 1;
	for (int i=L; i<=R; ++i) ans[prev][i] = idx;
	for (int i=prev_l; i<=L; ++i) ans[idx][i] = -ans[idx][0]-1;
	for (int i=R; i<=prev_r; ++i) ans[idx][i] = ans[idx][0]-2;
	L++; R--;
	if (L > R) return;
	if (R-L == 0){
		calc(idx,level+1,1,L-1,R+1,L,R,iter+1);
		return;
	}
	if (R-L <= 3){
		calc(idx,level+1,1,L-1,R+1,L,L+(R-L)/2,iter+1);
		calc(idx,level+1,2,L-1,R+1,R-(R-L)/2,R,iter+1);
		return;
	}
	int op = 1;
	if (0 <= (R-L)/3){
		calc(idx,level+1,op,L-1,R+1,L,L+(R-L)/3,iter+1);
		++op;
	}
	if (L+(R-L)/3+1 <= R-(R-L)/3-1){
		calc(idx,level+1,op,L-1,R+1,L+(R-L)/3+1,R-(R-L)/3-1,iter+1);
		++op;
	}
	if (0 <= (R-L)/3 and R-(R-L)/3 > L+(R-L)/3){
		calc(idx,level+1,op,L-1,R+1,R-(R-L)/3,R,iter+1);
		++op;
	}
}

vector<vector<int>> devise_strategy(int n){
	for (int i=0; i<21; ++i){
		ans.emplace_back(vector<int>(n+1));
	}
	calc(0,0,3,1,n,1,n,0);
	return ans;
}

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