Submission #652102

#	Time	Username	Problem	Language	Result	Execution time	Memory
652102		blue	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	1236 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; //'L' = left end, 'R' = right end, 
                     //'0' = part 0, '1' = part 1, '2' = part 2

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)
{
	// cerr << "build tree " << l << ' ' << r << ' ' << i << " : " << dp[i] << '\n';
	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;

	// for(int i = stp; i >= 1; i--)
	// 	cerr << dp[i] << " : " << spl[i] << '\n';
	// cerr << "\n\n\n\n";

	N = dp[stp];

	// cerr << "N value = " << N << '\n';

	addr = vector<string>(1+N, "");

	build_tree(1, N, stp);

	// cerr << "terminate\n";

	// for(int i = 1; i <= N; i++)
	// 	cerr << i << " : " << addr[i] << '\n';

	int x = dp[stp];


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

	vi depsiz;
	vi depspl;

	vvi depind;

	// cerr << "\n\n\n";

	for(int z = N; z >= 3; z = (z-2)/spl[inv[z]])
	{
		depsiz.push_back(z);
		depspl.push_back(spl[inv[z]]);
		// cerr << z << " : " << spl[inv[z]] << '\n';
	}
	// cerr << 2 << " : " << 1 << '\n';
	depsiz.push_back(2);
	depspl.push_back(1);

	// cerr << "\n\n\n";

	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++);
		}
	}
	// cerr << "u = " << u << '\n';

	// depind.push_back({{u++}});



	//person 0, checks A
	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' ];
		}
	}


// cerr << "done\n";

	// cerr << "sz = " << sz(depsiz) << '\n';

	for(int d = 0; d < sz(depsiz)-1; d++) 
	//even depth, check B         odd depth, check A
	{
		for(int z = 0; z < depspl[d]; z++)
		{
			int xi = depind[d][z];
			// cerr << d << ", " << z << " -> " << xi << '\n';
			// cerr << "xi = " << xi << '\n';
			//d even -> check A, odd -> check B

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

			for(int i = 1; i <= N; i++)
			{
				// cerr << "i = " << i << '\n';
				// if(xi == 1 && i == 9)
				// {
				// 	cerr << "z = " << z << '\n';
				// 	cerr << "hello, " << addr[i][d] << '\n';
				// }
				// cerr << "i = " << i << '\n';
				if(sz(addr[i]) - 1 < d)
				{
					res[xi][i] = 0;
				}
 				if(addr[i][d] == 'L')
				{
					// cerr << "case 1\n";
					if(d % 2 == 0)
						res[xi][i] = -2;
					else
						res[xi][i] = -1;
				}
				else if(addr[i][d] == 'R')
				{
					// cerr << "case 2\n";
					if(d % 2 == 0)
						res[xi][i] = -1;
					else
						res[xi][i] = -2;
				}
				else if(addr[i][d] - '0' < z)
				{
					if(d % 2 == 0)
						res[xi][i] = -2;
					else
						res[xi][i] = -1;
				}
				else if(addr[i][d] - '0' > z)
				{
					if(d % 2 == 0)
						res[xi][i] = -1;
					else
						res[xi][i] = -2;
				}
				else if(addr[i][d] - '0' == z)
				{
					// cerr << "case 3\n";
					// cerr << i << " : " << d+1 << ' ' << sz(addr[i]) << '\n';
					if(addr[i][d+1] == 'L')
					{
						if(d % 2 == 0)
							res[xi][i] = -2;
						else
							res[xi][i] = -1;
					}
					else if(addr[i][d+1] == 'R')
					{
						if(d % 2 == 0)
							res[xi][i] = -1;
						else
							res[xi][i] = -2;
					}
					else
						res[xi][i] = depind[d+1][addr[i][d+1] - '0'];
				}
			}

			// cerr << "z done\n";
		}

		// cerr << "d = " << d << " done\n";
	}

	// int ld = sz(depsiz) - 1;
	// int lx = stp-1;

	// cerr << "\n\n\n\n\n\n";

	// cerr << "ld = " << ld << '\n';

	// if(ld % 2 == 0)
	// {
	// 	res[ld][0] = 1;
	// 	for(int i = 1; i <= N; i++)
	// 	{
	// 		if(sz(addr[i]) - 1 < ld)
	// 		{
	// 			res[lx][i] = 0;
	// 		}
	// 		else if(addr[i][ld] == 'L')
	// 			res[lx][i] = -2;
	// 		else
	// 			res[lx][i] = -1;
	// 	}
	// }
	// else
	// {
	// 	res[ld][0] = 0;
	// 	for(int i = 1; i <= N; i++)
	// 	{
	// 		if(sz(addr[i]) - 1 < ld)
	// 		{
	// 			res[lx][i] = 0;
	// 		}
	// 		else if(addr[i][ld] == 'L')
	// 			res[lx][i] = -1;
	// 		else
	// 			res[lx][i] = -2;
	// 	}
	// }

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

	// cerr << "res size = " << sz(res) << '\n';
	// for(vi f : res)
	// cerr << sz(f) << '\n';

// cerr << "original N = " << N_ << '\n';



	// for(int xi = 0; xi < stp; xi++)
	// {
	// 	for(int u : res[xi])
	// 		cerr << u << ' ';
	// 	cerr << '\n';
	// }

	// cerr << addr[7] << "\n" << addr[8] << '\n';

	// cerr << "columns\n";
	// for(int xv = 0; xv < stp; xv++)
	// 	cerr << res[xv][7] << ' ' << res[xv][8] << '\n';
	// cerr << "\n\n";


	return res;
}

Compilation message (stderr)

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

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