Submission #643724

#	Time	Username	Problem	Language	Result	Execution time	Memory
643724		blue	Prisoner Challenge (IOI22_prison)	C++17	80 / 100	13 ms	1108 KiB

prison

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

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
#define sz(x) int(x.size())

const int lg = 8;
vi pow3 = vi(1 + lg);

int getdigit(int i, int d)
{
	if(d < 0)
		return 0;
	return (i / pow3[d]) % 3;
}

vvi devise_strategy(int N)
{
	pow3[0] = 1;
	for(int e = 1; e <= lg; e++)
		pow3[e] = 3 * pow3[e-1];

	vvi s(3*lg+1, vi(1+N, -1));

	s[0][0] = 0;
	for(int i = 1; i <= N; i++)
	{
		s[0][i] = 1 + getdigit(i, lg-1);
	}

	// int lstval = 3*lg;

	for(int p = 0; p < lg; p++)
	{
		int b = lg-1 - p;

		for(int d = 0; d < 3; d++)
			s[3*p + 1 + d][0] = !(p % 2);
		for(int i = 1; i <= N; i++)
		{
			int cd = getdigit(i, b); //current digit
			for(int wd = 0; wd <= 2; wd++) //whiteboard digit
			{
				if(cd < wd)
				{
					s[3*p + 1 + wd][i] = -2 + (p % 2);
				}
				else if(wd < cd)
				{
					s[3*p + 1 + wd][i] = -1 - (p % 2);
				}
				else
				{
					if(b-1 == 0 && getdigit(i, b-1) == 0)
						s[3*p + 1 + wd][i] = -2 + (p % 2);
					else if(b-1 == 0 && getdigit(i, b-1) == 2)
						s[3*p + 1 + wd][i] = -1 - (p % 2);
					else
						s[3*p + 1 + wd][i] = 3*(p+1) + 1 + getdigit(i, b-1);
				}
			}
		}
	}

	int x = sz(s) - 1;

	for(int i = 0; i < sz(s); i++)
	{
		for(int j = 0; j <= N; j++)
		{
			if(s[i][j] > x)
				s[i][j] = -1;
			assert(s[i][j] != x-2);
			assert(s[i][j] != x);
			if(s[i][j] == x-1)
				s[i][j] = x-2;
		}
	}

	s.pop_back();
	s.pop_back();
	x -= 2;

	// for(int i = 0; i <= x; i++)
	// {
	// 	for(int j = 0; j <= N; j++)
	// 	{
	// 		cerr << i << ' ' << j << " : " << s[i][j] << '\n';
	// 	}
	// }

	return s;
}

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