Submission #626734

#	Time	Username	Problem	Language	Result	Execution time	Memory
626734		galca	Prisoner Challenge (IOI22_prison)	C++17	72 / 100	12 ms	1072 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;

	{
		// first 5 operations
		operation.push_back(0);
		int mask = 1 << 12;

		for (int i = 1; i <= N; i++) {
			if ((i & mask) == mask) {
				operation.push_back(1);
			}
			else {
				int val = (i >> 10) & 0x3;
				operation.push_back(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);
			}
			else {
				operation.push_back(-2);
			}
		}
		res.push_back(operation);
		operation.erase(operation.begin(), operation.end());

		// if a prisoner gets 2-5
		for (int j = 2; j <= 5; j++) {
			operation.push_back(1);
			for (int i = 1; i <= N; i++) {
				int checkBit = (i >> 12) & 0x1;
				if (checkBit == 1) {
					operation.push_back(-1);
				}
				else {
					int bitsB = (i >> 10) & 0x3;
					int bitsA = j - 2;
					if (bitsA < bitsB) {
						operation.push_back(-1);
					}
					else if (bitsB < bitsA) {
						operation.push_back(-2);
					}
					else {
						int myBit = (i >> 9) & 0x1;
						int opcode = 6 + myBit;
						operation.push_back(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++) {
				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);
					}
					else {
						if (checkBit == 1) {
							operation.push_back(bag == 0 ? -2 : -1);
						}
						else {
							operation.push_back(bag == 0 ? -1 : -2);
						}
					}
				}

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

		for (int k = 0; k < 2; k++) {
			operation.push_back(1);
			for (int i = 1; i <= N; i++) {
				int checkBit = (i >> 2) & 0x1;

				if (checkBit < k) {
					operation.push_back(-2);
				}
				else if (checkBit > k) {
					operation.push_back(-1);
				}
				else {
					int myBits = (i & 0x3);
					if (myBits == 0) {
						operation.push_back(-2);
					}
					else if (myBits == 3) {
						operation.push_back(-1);
					}
					else if (myBits == 1) {
						operation.push_back(8 + offset * 2);
					}
					else if (myBits == 2) {
						operation.push_back(8 + offset * 2 + 1);
					}
				}
			}
			res.push_back(operation);
			operation.erase(operation.begin(), operation.end());
		}
		// last 2
		// got 1, he has 01 
		operation.push_back(0);
		for (int i = 1; i <= N; i++) {
			if ((i & 0x3) >= 1) {
				operation.push_back(-2);
			}
			else {
				operation.push_back(-1);
			}
		}
		res.push_back(operation);
		operation.erase(operation.begin(), operation.end());

		// got 2
		operation.push_back(0);
		for (int i = 1; i <= N; i++) {
			if ((i & 0x3) >= 2) {
				operation.push_back(-2);
			}
			else {
				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: 62 / 90