oj.uz

Submission #961433

# Submission time Handle Problem Language Result Execution time Memory
961433 2024-04-12T05:44:04 Z ____m___pl Prisoner Challenge (IOI22_prison) C++17
100 / 100
 11 ms 1372 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 levelOfNumberOnWhiteboard = levelInTreeOfNumberOnWhiteboard[numberOnWhiteboard];
		const int direction = whichDirection[numberOnWhiteboard];

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

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

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

			if (whichSonOfNode[nodeOfMyCoinsInBag] != direction && !ifNodeBelongsToNodeRangeAtLevel[coinsInBag][levelOfNumberOnWhiteboard]) {
				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(levelOfNumberOnWhiteboard == 7) {
					prisonerBehaviourIfRead_i_AsWhiteboardAnd_j_coinsInBag[numberOnWhiteboard][coinsInBag] = 20;
					continue;
				}

				int newNumber = numberOnWhiteboard;
				while (levelInTreeOfNumberOnWhiteboard[newNumber] == levelOfNumberOnWhiteboard) {
					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;
}

Subtask #1
5.0 / 5.0

# 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 2 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 2 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 816 KB Output is correct
9 Correct 2 ms 860 KB Output is correct

Subtask #2
5.0 / 5.0

# 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 2 ms 1112 KB Output is correct
6 Correct 2 ms 856 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 864 KB Output is correct

Subtask #3
90.0 / 90.0

# 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 4 ms 1120 KB Output is correct
5 Correct 7 ms 1368 KB Output is correct
6 Correct 10 ms 1372 KB Output is correct
7 Correct 11 ms 1372 KB Output is correct
8 Correct 1 ms 824 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 1112 KB Output is correct
12 Correct 8 ms 1368 KB Output is correct