제출 #626682

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
626682		galca	죄수들의 도전 (IOI22_prison)	C++17	0 / 100	1 ms	212 KiB

prison

#include "prison.h"

#include <vector>

std::vector<std::vector<int>> devise_strategy(int N) {
	std::vector<int> operation;
	// 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);
		}
	}
	std::vector<std::vector<int>> res;
	res.push_back(operation);
	operation.erase(operation.begin(), operation.end());

	// if a prisoner gets 1
	operation.push_back(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 bitsB = (i >> 10) & 0x3;
			int bitsA = j - 2;
			if (bitsA < bitsB) {
				operation.push_back(-1);
			}
			else if (bitsB < bitsA) {
				operation.push_back(-1);
			}
			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 >= 3; 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(-1);
					}
					else {
						operation.push_back(-2);
					}
				}
			}

			res.push_back(operation);
			operation.erase(operation.begin(), operation.end());
		}
		++offset;
	}
	for (int k = 0; k < 2; k++) {
		operation.push_back(0);
		for (int i = 1; i <= N; i++) {
			int checkBit = (i >> 3) & 0x1;
			
			if (checkBit < k) {
				operation.push_back(-2);
			}
			else if (checkBit > k) {
				operation.push_back(-1);
			}
			else {
				int myBits = (i >> 2) & 0x3;
				if (myBits == 0) {
					operation.push_back(-1);
				}
				else if (myBits == 3) {
					operation.push_back(-2);
				}
				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 or 00
	operation.push_back(1);
	for (int i = 1; i <= N; i++) {
		if ((i & 0x3) >= 1) {
			operation.push_back(-1);
		}
		else {
			operation.push_back(-2);
		}
	}
	res.push_back(operation);
	operation.erase(operation.begin(), operation.end());

	// got 2
	operation.push_back(1);
	for (int i = 1; i <= N; i++) {
		if ((i & 0x3) >= 2) {
			operation.push_back(-1);
		}
		else {
			operation.push_back(-2);
		}
	}
	res.push_back(operation);
	operation.erase(operation.begin(), operation.end());

	return res;
}

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