제출 #1074351

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

prison

#include <bits/stdc++.h>
#include "prison.h"
#define ll long long
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
 
template<typename T> bool ckmin(T &a, const T &b ) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b ) { return a < b ? a = b, 1 : 0; }
 
std::vector<std::vector<int>> devise_strategy(int N) {
	int req = 0, cur = 1;
	while (cur < N) cur *= 3, req++;
	// req bits
	// [1, N]
	vector<vector<int>> ans(req*4, vector<int>(N+1));
	auto split = [&](int x) {
		vector<int> res;
		while (x) {
			res.push_back(x % 3);
			x /= 3;
		}
		while (sz(res) < req) res.emplace_back(0);
		reverse(all(res));
		return res;
	};
	vector<vector<int>> val(N);
	for (int i = 0; i < N; i++) val[i] = split(i);
	for (int i = 0; i < req*4; i++) {
		if (!i) {
			ans[i][0] = 0;
			for (int j = 1; j <= N; j++) ans[i][j] = (req - 1) * 4 + 1 + val[j-1][0];
		}
		else {
			int bit = req - ((i - 1) / 4) - 1;
			if (bit == 0) {
				ans[i][0] = 1;
				assert(i % 4);
				int v = i % 4 == 1 ? 0 : i % 4 == 2 ? 1 : 2;
				for (int j = 1; j <= N; j++) {
					if (val[j-1][bit] != v) {
						ans[i][j] = val[j-1][bit] < v ? -2 : -1;
					}
					else {
						ans[i][j] = (i - 1) / 4 == 0 ? 0 : ((i - 1) / 4 - 1) * 4 + 1;
					}
				}
			}
			else {
				if (i % 4 == 1) {
					ans[i][0] = 0;
					for (int j = 1; j <= N; j++) {
						ans[i][j] = i + val[j-1][bit] + 1;
					}
				}
				else {
					ans[i][0] = 1;
					int v = i % 4 == 2 ? 0 : i % 4 == 3 ? 1 : 2;
					for (int j = 1; j <= N; j++) {
						if (val[j-1][bit] != v) {
							ans[i][j] = val[j-1][bit] < v ? -2 : -1;
						}
						else {
							ans[i][j] = (i - 1) / 4 == 0 ? 0 : ((i - 1) / 4 - 1) * 4 + 1;
						}
					}
				}
			}
		}
	}
	return ans;
}

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