oj.uz

Submission #960660

# Submission time Handle Problem Language Result Execution time Memory
960660 2024-04-10T20:17:27 Z ____m___pl Prisoner Challenge (IOI22_prison) C++17
100 / 100
 10 ms 1884 KB 
#include <bits/stdc++.h>
using namespace std;
 
constexpr int MAX_NUMBER_OF_COINS = 5000;
constexpr int LEVELS = 30;
 
pair<int,int> nodeRange[MAX_NUMBER_OF_COINS + 1];
int nodeToWhichValueAtLevelBelongs[MAX_NUMBER_OF_COINS + 1][LEVELS];
bool ifNodeBelongsToNodeRangeAtLevel[MAX_NUMBER_OF_COINS + 1][LEVELS];
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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1328 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 2 ms 1372 KB Output is correct
9 Correct 2 ms 1372 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1628 KB Output is correct
4 Correct 2 ms 1372 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1368 KB Output is correct
9 Correct 2 ms 1372 KB Output is correct

Subtask #3
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 5 ms 1628 KB Output is correct
5 Correct 8 ms 1840 KB Output is correct
6 Correct 9 ms 1880 KB Output is correct
7 Correct 10 ms 1884 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 2 ms 1368 KB Output is correct
10 Correct 2 ms 1372 KB Output is correct
11 Correct 5 ms 1628 KB Output is correct
12 Correct 9 ms 1884 KB Output is correct