Submission #1191648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191648		MateiKing80	Prisoner Challenge (IOI22_prison)	C++20	65 / 100	10 ms	1736 KiB

prison

#include <bits/stdc++.h>

using namespace std;

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

void build(int pos, int bit, int care, bool other, int nxt)
{
	last = max(last, pos);
	if (pos == 0)
	{
		ans[0][0] = 0;
		for (int i = 1; i <= n; i ++)
		{
			if (i & (1 << bit))
				ans[0][i] = 2;
			else
				ans[0][i] = 1;
		}
		build (1, 12, 1, 0, 3);
		build (2, 12, 1, 1, 3);
		return;
	}
	else
	{
		ans[pos][0] = care;
		for (int i = 1; i <= n; i ++)
		{
			if (i & (1 << bit) && !other) //castiga other
				ans[pos][i] = - (1 - care) - 1;
			else if (!(i & (1 << bit)) && other)
				ans[pos][i] = - care - 1;
			else if (i & (1 << (bit - 1)))
			{
				if (bit == 1) //castiga alalalt
					ans[pos][i] = - (1 - care) - 1;
				else
					ans[pos][i] = nxt + 1;
			}
			else //if (!(i & (1 << (bit - 1))))
			{
				if (bit == 1) //castig eu
					ans[pos][i] = - care - 1;
				else
					ans[pos][i] = nxt;
			}
		}
		
		if (other == 1 && bit > 1)
		{
			build (nxt, bit - 1, 1 - care, 0, nxt + 2);
			build (nxt + 1, bit - 1, 1 - care, 1, nxt + 2);
		}
	}
}

vector<vector<int>> devise_strategy(int _n)
{
	n = _n;
	build (0, 12, 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: 55 / 90