제출 #1191664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191664		MateiKing80	Prisoner Challenge (IOI22_prison)	C++20	80 / 100	7 ms	1640 KiB

prison

#include <bits/stdc++.h>

using namespace std;

const int N = 5000;
int n, last = 0;
int ans[N + 5][N + 5];

int b3(int x, int bit)
{
	while (bit --)
		x /= 3;
	return x % 3;
}

void build(int pos, int bit, int care, int other, int nxt) //schimbare la baza 3 now
{
	last = max(last, pos);
	if (pos == 0)
	{
		ans[0][0] = 0;
		for (int i = 1; i <= n; i ++)
			ans[0][i] = 1 + b3(i, bit);
		build (1, 7, 1, 0, 4);
		build (2, 7, 1, 1, 4);
		build (3, 7, 1, 2, 4);
		return;
	}
	else if (bit == 0)
	{
		ans[pos][0] = care;
		for (int i = 1; i <= n; i ++)
		{
			int x = b3(i, bit);
			if (x == 0)
				ans[pos][i] = - care - 1;
			else
				ans[pos][i] = - (1 - care) - 1;
		}
		return;
	}
	else
	{
		ans[pos][0] = care;
		for (int i = 1; i <= n; i ++)
		{
			if (b3(i, bit) > other) //castiga other
				ans[pos][i] = - (1 - care) - 1;
			else if (b3(i, bit) < other)
				ans[pos][i] = - care - 1;
			else if (bit == 1)
			{
				int x = b3(i, bit - 1);
				if (x == 0) //castig eu
					ans[pos][i] = - care - 1;
				else if (x == 2)
					ans[pos][i] = - (1 - care) - 1;
				else
					ans[pos][i] = nxt;
			}
			else
				ans[pos][i] = nxt + b3(i, bit - 1);
		}
		
		if (other == 1 && bit > 1)
		{
			build (nxt, bit - 1, 1 - care, 0, nxt + 3);
			build (nxt + 1, bit - 1, 1 - care, 1, nxt + 3);
			build (nxt + 2, bit - 1, 1 - care, 2, nxt + 3);
		}
		else if (bit == 1)
			build (nxt, 0, 1 - care, 1, nxt);
	}
}

vector<vector<int>> devise_strategy(int _n)
{
	n = _n;
	build (0, 7, 0, 0, 0);
	vector<vector<int>> strat(last + 1, vector<int>(n + 1));
	for (int i = 0; i <= last; i ++)
		for (int j = 0; j <= n; j ++)
			strat[i][j] = ans[i][j];
	return strat;
}
/*
int main()
{
	int n, a, b, tabla = 0;
	cin >> n >> a >> b;
	auto st = devise_strategy(n);
	while (1)
	{
		cout << tabla << '\n';
		int ntabla = 0;
		if (st[tabla][0] == 0) //citeste din a
			ntabla = st[tabla][a];
		else
			ntabla = st[tabla][b];
		if (ntabla < 0)
		{
			cout << -ntabla << '\n';
			exit(0);
		}
		tabla = ntabla;
	}
}
*/

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