제출 #833464

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
833464		pavement	죄수들의 도전 (IOI22_prison)	C++17	30 / 100	21 ms	1720 KiB

prison

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

#define mp make_pair

using ii = pair<int, int>;

const int b = 13;

vector<vector<int> > devise_strategy(int N) {
	int x = 3 * (b + 1) - 1;
	vector<vector<int> > s(x + 1, vector<int>(N + 1));
	
	auto unpack = [&](int v) {
		int b_bit = v / 3, state = v % 3;
		return mp(b - b_bit, state);
	};
	
	auto pack = [&](int bit, int state) {
		return (b - bit) * 3 + state;
	};
	
	for (int i = 0; i <= x; i++) {
		auto [bit, state] = unpack(i);
		if (state == 0) {
			s[i][0] = 0;
			for (int j = 1; j <= N; j++) {
				if (j & (1 << bit)) {
					// write (bit, 1, 1)
					s[i][j] = pack(bit, 2);
				} else {
					// write (bit, 1, 0)
					s[i][j] = pack(bit, 1);
				}
			}
		} else {
			s[i][0] = 1;
			for (int j = 1; j <= N; j++) {
				if (j & (1 << bit)) {
					if (state == 1) {
						s[i][j] = -1;
					} else {
						if (bit == 0) {
							s[i][j] = 0;
						} else {
							// write (bit - 1, 0)
							s[i][j] = pack(bit - 1, 0);
						}
					}
				} else {
					if (state == 2) {
						s[i][j] = -2;
					} else {
						if (bit == 0) {
							s[i][j] = 0;
						} else {
							// write (bit - 1, 0)
							s[i][j] = pack(bit - 1, 0);
						}
					}
				}
			}
		}
	}
	return s;
}

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