Submission #1244094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244094		amine_aroua	Prisoner Challenge (IOI22_prison)	C++20	65 / 100	8 ms	1608 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>
using namespace std;
const int C = 24;
vector<vector<int>> base3;
vector<int> get_base3(int x)
{
	vector<int> v;
	while(x)
	{
		v.push_back(x%3);
		x/=3;
	}
	while((int)v.size() != 8)
		v.push_back(0);
	return v;
}
int get_idx(int bit , int val)
{
	return bit * 3 + val + 1;
}
std::vector<std::vector<int>> devise_strategy(int N) 
{
	vector<vector<int>> s(C + 1 ,vector<int>(N + 1));
	base3.assign(N+1 , {});
	s[0][0] = 0;
	for(int i = 1 ; i <= N ; i++)
	{
		base3[i] = get_base3(i);
		s[0][i] = get_idx(7 , base3[i][7]);
		// cout<<s[0][i]<<'\n';
	}
	for(int i = 7 ; i >= 0 ; i--)
	{
		for(int j = 0 ; j < 3 ; j++)
		{
			int idx = get_idx(i , j);
			s[idx][0] = (i % 2);
			// cout<<s[idx][0]<<'\n';
			for(int k = 1 ; k <= N ; k++)
			{
				int cj = base3[k][i];
				if(cj == j && i != 0)
				{
					s[idx][k] = get_idx(i - 1 , base3[k][i - 1]);
				}
				else if(j < cj)
				{
					s[idx][k] = (i%2) - 2;
				}
				else
					s[idx][k] = (-1) -(i % 2) ;
			}
		}
	}
	// for(int i = 0 ;i <= C ; i++)
	// {
	// 	for(int j = 0 ; j <= N ; j++)
	// 	{
	// 		cout<<s[i][j]<<" ";
	// 	}
	// 	cout<<'\n';
	// }
	return s;
}

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