Submission #960663

# Submission time Handle Problem Language Result Execution time Memory
960663 2024-04-10T20:30:18 Z ____m___pl Prisoner Challenge (IOI22_prison) C++17
100 / 100
9 ms 1540 KB
#include <bits/stdc++.h>
using namespace std;

constexpr int MAX_NUMBER_OF_COINS = 5000;
constexpr int LEVELS = 8;

pair<int,int> nodeRange[MAX_NUMBER_OF_COINS + 1];
int nodeToWhichValueAtLevelBelongs[MAX_NUMBER_OF_COINS + 1][LEVELS + 1];
bool ifNodeBelongsToNodeRangeAtLevel[MAX_NUMBER_OF_COINS + 1][LEVELS + 1];
vector<int> sonsOfNode[MAX_NUMBER_OF_COINS + 1];
int whichSonOfNode[MAX_NUMBER_OF_COINS + 1];
int nodeIndex = 0;

void insertNodeAndFillTree(const int node, const int level, int a, int b){
	nodeRange[node] = {a, b};

	for (int valueFromInterval = a; valueFromInterval <= b; ++valueFromInterval) {
		nodeToWhichValueAtLevelBelongs[valueFromInterval][level] = node;
	}

	for (int levelIterator = level + 1; levelIterator <= LEVELS; ++levelIterator) {
		nodeToWhichValueAtLevelBelongs[a][levelIterator] = nodeToWhichValueAtLevelBelongs[b][levelIterator] = node;
		ifNodeBelongsToNodeRangeAtLevel[a][levelIterator] = ifNodeBelongsToNodeRangeAtLevel[b][levelIterator] = true;
	}

	a++;
	b--;
	if(a > b) {
		return;
	}

	if (level < 5) {
		const int c = a + (b - a) / 3;
		const int d = b - (b - a) / 3;

		if (a <= c) {
			sonsOfNode[node].push_back(++nodeIndex);
			whichSonOfNode[nodeIndex] = 0;
			insertNodeAndFillTree(nodeIndex, level + 1, a, c);
		}
		if (c + 1 <= d) {
			sonsOfNode[node].push_back(++nodeIndex);
			whichSonOfNode[nodeIndex] = 1;
			insertNodeAndFillTree(nodeIndex, level + 1, c + 1, d);
		}
		if (d + 1 <= b) {
			sonsOfNode[node].push_back(++nodeIndex);
			whichSonOfNode[nodeIndex] = 2;
			insertNodeAndFillTree(nodeIndex, level + 1, d + 1, b);
		}
	} else {
		const int c = (a + b) / 2;
		if (a <= c) {
			sonsOfNode[node].push_back(++nodeIndex);
			whichSonOfNode[nodeIndex] = 0;
			insertNodeAndFillTree(nodeIndex, level + 1, a, c);
		}
		if (c + 1 <= b) {
			sonsOfNode[node].push_back(++nodeIndex);
			whichSonOfNode[nodeIndex] = 1;
			insertNodeAndFillTree(nodeIndex, level + 1, c + 1, b);
		}
	}
}

vector<vector<int>> devise_strategy(int N){
	insertNodeAndFillTree(++nodeIndex, 0, 1, 5000);

	vector<vector<int> > prisonerBehaviourIfRead_i_AsWhiteboardAnd_j_coinsInBag(21);
	vector<int> levelInTreeOfNumberOnWhiteboard(21);
	vector<int> whichDirection(21);

	levelInTreeOfNumberOnWhiteboard[0] = whichDirection[0] = 0;
	for (int i = 0; i < 5; ++i) {
		for (int j = 0; j < 3; ++j) {
			levelInTreeOfNumberOnWhiteboard[1 + i * 3 + j] = i + 1;
			whichDirection[1 + i * 3 + j] = j;
		}
	}
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j) {
			levelInTreeOfNumberOnWhiteboard[16 + i * 2 + j] = i + 6;
			whichDirection[16 + i * 2 + j] = j;
		}
	}
	levelInTreeOfNumberOnWhiteboard[20] = 8;
	whichDirection[20] = 0;


	for (int numberOnWhiteboard = 0; numberOnWhiteboard < 21; numberOnWhiteboard++){
		const int level = levelInTreeOfNumberOnWhiteboard[numberOnWhiteboard];
		const int direction = whichDirection[numberOnWhiteboard];

		prisonerBehaviourIfRead_i_AsWhiteboardAnd_j_coinsInBag[numberOnWhiteboard].resize(N + 1);
		prisonerBehaviourIfRead_i_AsWhiteboardAnd_j_coinsInBag[numberOnWhiteboard][0] = level % 2;

		int visibleBag = -1;
		int inVisibleBag = -2;
		if (level % 2) {
			visibleBag = -2;
			inVisibleBag = -1;
		}

		for (int coinsInBag = 1; coinsInBag <= N; coinsInBag++){
			const int nodeOfMyCoinsInBag = nodeToWhichValueAtLevelBelongs[coinsInBag][level];
			const int a = nodeRange[nodeOfMyCoinsInBag].first;
			const int b = nodeRange[nodeOfMyCoinsInBag].second;

			if (whichSonOfNode[nodeOfMyCoinsInBag] != direction && !ifNodeBelongsToNodeRangeAtLevel[coinsInBag][level]){
				if (whichSonOfNode[nodeOfMyCoinsInBag] < direction) {
					prisonerBehaviourIfRead_i_AsWhiteboardAnd_j_coinsInBag[numberOnWhiteboard][coinsInBag] = visibleBag;
				} else {
					prisonerBehaviourIfRead_i_AsWhiteboardAnd_j_coinsInBag[numberOnWhiteboard][coinsInBag] = inVisibleBag;
				}
			} else if (coinsInBag == a) {
				prisonerBehaviourIfRead_i_AsWhiteboardAnd_j_coinsInBag[numberOnWhiteboard][coinsInBag] = visibleBag;
			} else if (coinsInBag == b) {
				prisonerBehaviourIfRead_i_AsWhiteboardAnd_j_coinsInBag[numberOnWhiteboard][coinsInBag] = inVisibleBag;
			} else {
				if (level == 7) {
					prisonerBehaviourIfRead_i_AsWhiteboardAnd_j_coinsInBag[numberOnWhiteboard][coinsInBag] = 20;
					continue;
				}

				int newNumber = numberOnWhiteboard;
				while (levelInTreeOfNumberOnWhiteboard[newNumber] == levelInTreeOfNumberOnWhiteboard[numberOnWhiteboard]) {
					newNumber++;
				}

				prisonerBehaviourIfRead_i_AsWhiteboardAnd_j_coinsInBag[numberOnWhiteboard][coinsInBag] = newNumber;
				if (sonsOfNode[nodeOfMyCoinsInBag].size() > 1 && nodeRange[sonsOfNode[nodeOfMyCoinsInBag][1]].first <= coinsInBag){
					prisonerBehaviourIfRead_i_AsWhiteboardAnd_j_coinsInBag[numberOnWhiteboard][coinsInBag]++;
				}
				if (sonsOfNode[nodeOfMyCoinsInBag].size() > 2 && nodeRange[sonsOfNode[nodeOfMyCoinsInBag][2]].first <= coinsInBag){
					prisonerBehaviourIfRead_i_AsWhiteboardAnd_j_coinsInBag[numberOnWhiteboard][coinsInBag]++;
				}
			}
		}
	}

	return prisonerBehaviourIfRead_i_AsWhiteboardAnd_j_coinsInBag;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 684 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 9 ms 1368 KB Output is correct
7 Correct 9 ms 1484 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 4 ms 1116 KB Output is correct
12 Correct 7 ms 1540 KB Output is correct