제출 #627289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
627289		Noam527	죄수들의 도전 (IOI22_prison)	C++17	65 / 100	13 ms	1108 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<std::vector<int>> devise_strategy(int N) {
	const int LAYERS = 8;
	int pw[LAYERS] = { 1 };
	for (int i = 1; i < LAYERS; i++) pw[i] = 3 * pw[i - 1];

	auto trit = [&pw](int value, int index) {
		return value / pw[index] % 3;
	};

	vector<vector<int>> s(3 * LAYERS + 1, vector<int>(N + 1));
	// initialize 0
	s[0][0] = 0; // bag A
	for (int seen = 1; seen <= N; seen++)
		s[0][seen] = 1 + trit(seen, LAYERS - 1);
	// rest of the layers
	for (int layer = 1; layer <= LAYERS; layer++) {
		int low = 3 * layer - 2;
		int high = 3 * layer;
		for (int board = low; board <= high; board++) {
			int realboard = (board - 1) % 3; // what the board represents
			s[board][0] = layer & 1;
			for (int seen = 1; seen <= N; seen++) {
				int realseen = trit(seen, LAYERS - 1 - layer + 1);
				if (realboard != realseen) {
					// can deduce
					if (realboard < realseen) {
						if (layer & 1)
							s[board][seen] = -1;
						else
							s[board][seen] = -2;
					}
					else {
						if (layer & 1)
							s[board][seen] = -2;
						else
							s[board][seen] = -1;
					}
				}
				else {
					// equal
					if (layer != LAYERS)
						s[board][seen] = low + 3 + trit(seen, LAYERS - 1 - layer);
					else
						s[board][seen] = 0; // won't really happen
				}
			}
		}
	}
	return s;
}

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