Submission #1319175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319175		dnnnda	Prisoner Challenge (IOI22_prison)	C++20	47 / 100	9 ms	1336 KiB

prison

#include "prison.h"

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

std::vector<std::vector<int>> devise_strategy(int N) {
	vector<int> po3={1,3,9,27,81,243,729,2187,6561};
	vector<vector<int>> ret(33,vector<int>(N+1));
	ret[0][0]=0;
	for(int i=0 ; i<=3 ; i++) for(int j=0 ; j<=7 ; j++){
		ret[j*4+i+1][0]=(i==3 ? 0 : 1);
	}
	for(int j=1 ; j<=N ; j++){
		ret[0][j]=7*4+j/2187+1;
	}
	for(int i=1 ; i<=32 ; i++) for(int j=1 ; j<=N ; j++){
		int rd=(i-1)/4, re=(i-1)%4;
		if(re==3) ret[i][j]=rd*4+j/(po3[rd])%3+1;
		else{
			int temp=j/(po3[rd])%3;
			if(temp<re) ret[i][j]=-2;
			else if(temp>re) ret[i][j]=-1;
			else ret[i][j]=(rd-1)*4+3+1;
		}
	}


	return ret;
}

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