Submission #1130832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130832		alosza	Prisoner Challenge (IOI22_prison)	C++20	100 / 100	14 ms	1096 KiB

prison

#include "prison.h"

#include <bits/stdc++.h>

using namespace std;

const int x = 20;

vector<int> divs = {3, 3, 3, 3, 3, 2, 2, 1};
vector<int> indexs = {1, 4, 7, 10, 13, 16, 18, 20};
vector<int> AorB = {0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0};

int index0toOther(int AB) //0 - -1 1 - -2
{
	if(AB == 0) return -1;
	return -2;
}

void solve(int l, int r, int num, int index, vector<vector<int>>& table)
{
	int n = r - l + 1;
	if(n <= 2)
	{
		table[num][l] = index0toOther(AorB[num]);
		table[num][r] = index0toOther(1 - AorB[num]);
		return;
	}
	int intervalSize = (n + divs[index] - 3) / divs[index]; //n - 2 + divs[index] - 1;
	for(int i = l; i <= r; i++)
	{
		if(i == l) table[num][i] = index0toOther(AorB[num]);
		else if(i == r) table[num][i] = index0toOther(1 - AorB[num]);
		else
		{
			int numInterval = (i - l - 1) / intervalSize;
			table[num][i] = indexs[index] + numInterval;
		}
	}
	for(int i = 0; i < divs[index]; i++)
	{
		int nnum = indexs[index] + i;
		int nl = l + 1 + intervalSize * i, nr = min(r, l + intervalSize * (i + 1));
		for(int ii = l; ii < nl; ii++)
		{
			table[nnum][ii] = index0toOther(1 - AorB[num]);
		}
		solve(nl, nr, nnum, index + 1, table);
		for(int ii = nr+1; ii <= r; ii++)
		{
			table[nnum][ii] = index0toOther(AorB[num]);
		}
	}
}

vector<vector<int>> devise_strategy(int N)
{
	vector<vector<int>> res(x + 1);
	for(int i = 0; i <= x; i++)
	{
		res[i] = vector<int>(N + 1);
		res[i][0] = AorB[i];
	}
	solve(1, N, 0, 0, res);
	return res;
}

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