Submission #960662

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
960662	2024-04-10T20:28:34 Z	____m___pl	Prisoner Challenge (IOI22_prison)	C++17	Compilation error	0 ms	0 KB

prison

#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;
}


int main(){
    vector<vector<int> > strategy = devise_strategy(5000);

    int coins_A, coins_B;
    cin >> coins_A >> coins_B;

	int whiteboard = 0;
	while (true){
		int bag = strategy[whiteboard][0];

		int val = 0;
		if (bag == 0) {
			val = coins_A;
		} else {
			val = coins_B;
		}

		const int ruch2 = strategy[whiteboard][val];
		cout << "Tab: " << whiteboard << " ktory: " << bag << " val: " << val << " # " << strategy[whiteboard][val] <<"\n";

		whiteboard = strategy[whiteboard][val];

		if (ruch2 < 0) {
			exit(0);
		}
	}
}

Compilation message

/usr/bin/ld: /tmp/cczJBfRC.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccnH4XVA.o:prison.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status