Submission #652103

#	Time	Username	Problem	Language	Result	Execution time	Memory
652103		blue	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	12 ms	1272 KiB

prison

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

using vi = vector<int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())

const int stp = 21;
int N;

vector<string> addr;

vi dp(1+stp);
vi inv(1 + 6'000);
vi spl(1+stp);

vi dep;

void selfmax(int& a, int b)
{
	a = max(a, b);
}



void build_tree(int l, int r, int i)
{
	assert(l != r);

	addr[l].push_back('L');
	l++;

	addr[r].push_back('R');
	r--;

	if(i == 1)
	{
		return;
	}
	else if(i == 2)
	{
		addr[l].push_back('0');
		addr[l+1].push_back('0');
		build_tree(l, l+1, 1);
	}
	else
	{
		int k;

		if(dp[i] == 3*dp[i-3] + 2)
			k = 3;
		else
			k = 2;

		int j = (r-l+1)/k;


		for(int ki = 0; ki < k; ki++)
		{
			int l1 = l + j*ki;
			int r1 = l + j*(ki+1) - 1;

			for(int n = l1; n <= r1; n++)
				addr[n].push_back('0' + ki);

			build_tree(l1, r1, i-k);
		}
	}
}



vvi devise_strategy(int N_)
{
	dp[0] = -100;
	dp[1] = 2;
	dp[2] = 4;
	for(int i = 3; i <= stp; i++)
	{
		if(i-3 >= 1)
			selfmax(dp[i], 3*dp[i-3] + 2);

		if(i-2 >= 1)
			selfmax(dp[i], 2*dp[i-2] + 2);

		if(dp[i] == 3*dp[i-3] + 2)
			spl[i] = 3;
		else
			spl[i] = 2;
	}

	spl[2] = 1;
	spl[1] = 0;

	for(int i = 1; i <= stp; i++)
		inv[dp[i]] = i;


	N = dp[stp];
	addr = vector<string>(1+N, "");

	build_tree(1, N, stp);

	int x = dp[stp];


	vvi res(stp, vi(1+N, 0));

	vi depsiz;
	vi depspl;

	vvi depind;

	for(int z = N; z >= 3; z = (z-2)/spl[inv[z]])
	{
		depsiz.push_back(z);
		depspl.push_back(spl[inv[z]]);
	}
	depsiz.push_back(2);
	depspl.push_back(1);

	int u = 1;

	for(int d = 0; d < sz(depsiz)-1; d++)
	{
		depind.push_back({});
		for(int e = 0; e < depspl[d]; e++)
		{
			depind[d].push_back(u++);
		}
	}

	res[0][0] = 0;
	for(int i = 1; i <= N; i++)
	{
		if(addr[i][0] == 'L')
			res[0][i] = -1;
		else if(addr[i][0] == 'R')
			res[0][i] = -2;
		else
		{
			res[0][i] = depind[0][ addr[i][0] - '0' ];
		}
	}


	for(int d = 0; d < sz(depsiz)-1; d++) 
	{
		for(int z = 0; z < depspl[d]; z++)
		{
			int xi = depind[d][z];

			if(d % 2 == 0)
				res[xi][0] = 1;
			else 
				res[xi][1] = 0;

			for(int i = 1; i <= N; i++)
			{
				
				if(sz(addr[i]) - 1 < d)
				{
					res[xi][i] = 0;
				}
 				if(addr[i][d] == 'L') res[xi][i] = -2 + (d%2);
				else if(addr[i][d] == 'R') res[xi][i] = -1 - (d%2);
				else if(addr[i][d] - '0' < z) res[xi][i] = -2 + (d%2);
				else if(addr[i][d] - '0' > z) res[xi][i] = -1 - (d%2);
				else if(addr[i][d] - '0' == z)
				{
					if(addr[i][d+1] == 'L') res[xi][i] = -2 + (d%2);
					else if(addr[i][d+1] == 'R') res[xi][i] = -1 - (d%2);
					else
						res[xi][i] = depind[d+1][addr[i][d+1] - '0'];
				}
			}
		}
	}

	for(int xi = 0; xi < stp; xi++)
		res[xi].resize(1+N_);

	return res;
}

Compilation message (stderr)

prison.cpp: In function 'vvi devise_strategy(int)':
prison.cpp:105:6: warning: unused variable 'x' [-Wunused-variable]
  105 |  int x = dp[stp];
      |      ^

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