Submission #638210

#	Time	Username	Problem	Language	Result	Execution time	Memory
638210		blue	Prisoner Challenge (IOI22_prison)	C++17	38 / 100	19 ms	1620 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 = 13;

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

	

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

		s[3*p + 0][0] = 0; //check A
		for(int i = 1; i <= N; i++)
			s[3*p + 0][i] = 3*p + 1 + bool(i & (1<<b));

		s[3*p + 1][0] = 1; //A has bit 0
		for(int i = 1; i <= N; i++)
		{
			if(i & (1<<b))
				s[3*p + 1][i] = -1;
			else
				s[3*p + 1][i] = 3*(p+1) + 0;
		}

		s[3*p + 2][0] = 1; //A has bit 1
		for(int i = 1; i <= N; i++)
		{
			if(i & (1<<b))
			{
				s[3*p + 2][i] = 3*(p+1) + 0;
			}
			else
			{
				s[3*p + 2][i] = -2;
			}
		}
	}

	// for(int i = 0; i < 3*lg; i++)
	// {
	// 	for(int j = 0; j <= N; j++)
	// 	{
	// 		cerr << s[i][j] << ' ';
	// 	}
	// 	cerr << '\n';
	// }

	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;

	return s;
}

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