Submission #828145

#	Time	Username	Problem	Language	Result	Execution time	Memory
828145		ttamx	Prisoner Challenge (IOI22_prison)	C++17	51.50 / 100	13 ms	1252 KiB

prison

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

using namespace std;

const int N=5005;

int n;

vector<vector<int>> devise_strategy(int _n){
	n=_n;
	int x=29;
	vector<int> pw(8);
	pw[0]=1;
	for(int i=1;i<9;i++)pw[i]=pw[i-1]*3;
	vector<vector<int>> s(x+1,vector<int>(n+1));
	int id=0;
	for(int i=7;i>=1;i--){
		s[id][0]=0;
		for(int j=1;j<=n;j++){
			int val=j/pw[i]%3;
			s[id][j]=id+val+1;
		}
		id++;
		s[id][0]=1;
		for(int j=1;j<=n;j++){
			int val=j/pw[i]%3;
			if(val==0){
				s[id][j]=id+3;
			}else{
				s[id][j]=-1;
			}
		}
		id++;
		s[id][0]=1;
		for(int j=1;j<=n;j++){
			int val=j/pw[i]%3;
			if(val==1){
				s[id][j]=id+2;
			}else if(val==2){
				s[id][j]=-1;
			}else{
				s[id][j]=-2;
			}
		}
		id++;
		s[id][0]=1;
		for(int j=1;j<=n;j++){
			int val=j/pw[i]%3;
			if(val==2){
				s[id][j]=id+1;
			}else{
				s[id][j]=-2;
			}
		}
		id++;
	}
	s[id][0]=0;
	for(int j=1;j<=n;j++){
		int val=j%3;
		if(val==0){
			s[id][j]=-1;
		}else if(val==2){
			s[id][j]=-2;
		}else{
			s[id][j]=id+1;
		}
	}
	id++;
	s[id][0]=1;
	for(int j=1;j<=n;j++){
		int val=j%3;
		if(val==0){
			s[id][j]=-2;
		}else{
			s[id][j]=-1;
		}
	}
	return s;
}

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