Submission #828256

#	Time	Username	Problem	Language	Result	Execution time	Memory
828256		ttamx	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	10 ms	1100 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;
	s[id][0]=0;
	for(int j=1;j<=n;j++){
		int val=j/pw[7]%3;
		s[id][j]=id+val+1;
	}
	id++;
	for(int i=7;i>=1;i--){
		int c=i&1;
		for(int x=0;x<3;x++){
			s[id][0]=c;
			for(int j=1;j<=n;j++){
				int val=j/pw[i]%3;
				if(val==x){
					int val2=j/pw[i-1]%3;
					s[id][j]=id+3-x+val2;
					if(i==1){
						if(val2==0)s[id][j]=-2;
						if(val2==2)s[id][j]=-1;
						if(val2==1)s[id][j]=id+3-x;
					}
				}else if(val>x){
					s[id][j]=c-2;
				}else{
					s[id][j]=-c-1;
				}
			}
			id++;
		}
	}
	s[id][0]=0;
	for(int j=1;j<=n;j++){
		int val=j%3;
		if(val==0){
			s[id][j]=-1;
		}else{
			s[id][j]=-2;
		}
	}
	s.resize(id+1);
	return s;
}

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