Submission #626730

#	Time	Username	Problem	Language	Result	Execution time	Memory
626730		galca	Prisoner Challenge (IOI22_prison)	C++17	10 / 100	10 ms	976 KiB

prison

#include "prison.h"

#include <vector>

std::vector<std::vector<int>> devise_strategy(int N) {
	std::vector<int> operation;
	std::vector<std::vector<int>> res;
	if (0)
	{
	operation.push_back(0);
	int mask = 1 << 12;
	//printf(" I am prisoner %d open bag A\n", res.size() + 1);
	for (int i = 1; i <= N; i++) {
		if ((i & mask) != mask) {
			operation.push_back(1);
			//printf(" if I see %d coins, I write 1\n", i);
		}
		else {
			operation.push_back(2);
			//printf(" if I see %d coins, I write 2\n", i);
		}
	}
	res.push_back(operation);
	operation.erase(operation.begin(), operation.end());

	// steady state
	int offset = 0;
	for (int j = 11; j >= 1; j--) {
		int bag = j & 0x1;

		for (int k = 0; k < 2; k++) {
			//printf(" I am prisoner %d open bag %s\n", res.size() + 1, bag == 0 ? "A" : "B");
			operation.push_back(bag);
			for (int i = 1; i <= N; i++) {
				int checkBit = (i >> (j + 1)) & 0x1;
				int passBit = (i >> j) & 0x1;
				if (checkBit == k) {
					int opcode = 3 + offset * 2 + passBit;
					operation.push_back(opcode);
					//printf(" if I see %d coins, I write %d\n", i, opcode);
				}
				else {
					if (checkBit == 1) {
						operation.push_back(bag == 0 ? -2 : -1);
						//printf(" if I see %d coins, I write B is heavier\n", i);
					}
					else {
						operation.push_back(bag == 0 ? -1 : -2);
						//printf(" if I see %d coins, I write A is heavier\n", i);
					}
				}
			}

			res.push_back(operation);
			operation.erase(operation.begin(), operation.end());
		}
		++offset;
	}

	for (int k = 0; k < 2; k++) {
		//printf(" I am prisoner %d open bag %s\n", res.size() + 1, bag == 0 ? "A" : "B");
		operation.push_back(0);
		for (int i = 1; i <= N; i++) {
			int checkBit = (i >> 1) & 0x1;
			int passBit = i & 0x1;
			if (checkBit == k) {
				if (passBit == 1) {
					operation.push_back(-2);
				}
				else {
					operation.push_back(-1);
				}
			}
			else {
				if (checkBit == 1) {
					operation.push_back(-2);
					//printf(" if I see %d coins, I write B is heavier\n", i);
				}
				else {
					operation.push_back(-1);
					//printf(" if I see %d coins, I write A is heavier\n", i);
				}
			}
		}

		res.push_back(operation);
		operation.erase(operation.begin(), operation.end());
	}

	return res;
}
	{
		// first 5 operations
		operation.push_back(0);
		int mask = 1 << 12;
		//printf(" I am prisoner %d open bag A\n", res.size() + 1);
		for (int i = 1; i <= N; i++) {
			if ((i & mask) == mask) {
				operation.push_back(1);
				//printf(" if I see %d coins, I write %d\n", i, 1);
			}
			else {
				int val = (i >> 10) & 0x3;
				operation.push_back(val + 2);
				//printf(" if I see %d coins, I write %d\n", i, val+2);
			}
		}

		res.push_back(operation);
		operation.erase(operation.begin(), operation.end());

		// if a prisoner gets 1
		operation.push_back(1);
		//printf(" I am prisoner %d open bag B\n", res.size() + 1);
		for (int i = 1; i <= N; i++) {
			if ((i & mask) == mask) {
				int myBit = (i >> 9) & 0x1;
				int opcode = 6 + myBit;
				operation.push_back(opcode);
				//printf(" if I see %d coins, I write %d\n", i, opcode);
			}
			else {
				operation.push_back(-2);
				//printf(" if I see %d coins, I write A is heavier\n", i);
			}
		}
		res.push_back(operation);
		operation.erase(operation.begin(), operation.end());

		// if a prisoner gets 2-5
		for (int j = 2; j <= 5; j++) {
			//printf(" I am prisoner %d open bag B\n", res.size() + 1);
			operation.push_back(1);
			for (int i = 1; i <= N; i++) {
				int bitsB = (i >> 10) & 0x3;
				int bitsA = j - 2;
				if (bitsA < bitsB) {
					operation.push_back(-1);
					//printf(" if I see %d coins, I write B is heavier\n", i);
				}
				else if (bitsB < bitsA) {
					operation.push_back(-2);
					//printf(" if I see %d coins, I write A is heavier\n", i);
				}
				else {
					int myBit = (i >> 9) & 0x1;
					int opcode = 6 + myBit;
					operation.push_back(opcode);
					//printf(" if I see %d coins, I write %d\n", i, opcode);
				}
			}
			res.push_back(operation);
			operation.erase(operation.begin(), operation.end());
		}

		// steady state
		int offset = 0;
		for (int j = 8; j >= 2; j--) {
			int bag = j & 0x1;

			for (int k = 0; k < 2; k++) {
				//printf(" I am prisoner %d open bag %s\n", res.size() + 1, bag == 0 ? "A" : "B");
				operation.push_back(bag);
				for (int i = 1; i <= N; i++) {
					int checkBit = (i >> (j + 1)) & 0x1;
					int passBit = (i >> j) & 0x1;
					if (checkBit == k) {
						int opcode = 8 + offset * 2 + passBit;
						operation.push_back(opcode);
						//printf(" if I see %d coins, I write %d\n", i, opcode);
					}
					else {
						if (checkBit == 1) {
							operation.push_back(bag == 0 ? -2 : -1);
							//printf(" if I see %d coins, I write B is heavier\n", i);
						}
						else {
							operation.push_back(bag == 0 ? -1 : -2);
							//printf(" if I see %d coins, I write A is heavier\n", i);
						}
					}
				}

				res.push_back(operation);
				operation.erase(operation.begin(), operation.end());
			}
			++offset;
		}

		for (int k = 0; k < 2; k++) {
			operation.push_back(1);
			//printf(" (pass last 2 a) I am prisoner %d open bag A\n", res.size() + 1);
			for (int i = 1; i <= N; i++) {
				int checkBit = (i >> 2) & 0x1;

				if (checkBit < k) {
					//printf(" if I see %d coins, I write A is heavier\n", i);
					operation.push_back(-2);
				}
				else if (checkBit > k) {
					//printf(" if I see %d coins, I write B is heavier\n", i);
					operation.push_back(-1);
				}
				else {
					int myBits = (i & 0x3);
					if (myBits == 0) {
						operation.push_back(-2);
						//printf(" if I see %d coins, I write B is heavier\n", i);
					}
					else if (myBits == 3) {
						operation.push_back(-1);
						//printf(" if I see %d coins, I write A is heavier\n", i);
					}
					else if (myBits == 1) {
						operation.push_back(8 + offset * 2);
						//printf(" if I see %d coins, I write %d\n", i, 8 + offset * 2);
					}
					else if (myBits == 2) {
						operation.push_back(8 + offset * 2 + 1);
						//printf(" if I see %d coins, I write %d\n", i, 8 + offset * 2 + 1);
					}
				}
			}
			res.push_back(operation);
			operation.erase(operation.begin(), operation.end());
		}
		// last 2
		// got 1, he has 01 or 00
		//printf(" (check last 2 a) I am prisoner %d open bag B\n", res.size() + 1);
		operation.push_back(0);
		for (int i = 1; i <= N; i++) {
			if ((i & 0x3) >= 1) {
				operation.push_back(-2);
				//printf(" if I see %d coins, I write B is heavier\n", i);
			}
			else {
				operation.push_back(-1);
				//printf(" if I see %d coins, I write A is heavier\n", i);
			}
		}
		res.push_back(operation);
		operation.erase(operation.begin(), operation.end());

		// got 2
		//printf("(check last 2 b) I am prisoner %d open bag B\n", res.size() + 1);
		operation.push_back(0);
		for (int i = 1; i <= N; i++) {
			if ((i & 0x3) >= 2) {
				operation.push_back(-2);
				//printf(" if I see %d coins, I write B is heavier\n", i);
			}
			else {
				////printf(" if I see %d coins, I write A is heavier\n", i);
				operation.push_back(-1);
			}
		}
		res.push_back(operation);
		operation.erase(operation.begin(), operation.end());

		return res;
	}
}

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