제출 #626020

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
626020		happypotato	죄수들의 도전 (IOI22_prison)	C++17	42.50 / 100	26 ms	1532 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll int, ll int>
#define ff first
#define ss second
#define pb push_back
vector<vector<int>> devise_strategy(int n) {
	vector<vector<int>> ret;
	const vector<int> go5 = {1, 5, 25, 125, 625, 3125, 15625};
	int x = 35;
	ret.resize(x + 1);
	for (int i = 0; i <= x; i++) ret[i].resize(n + 1);
	// write 0
	ret[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		ret[0][i] = 25 + (i / go5[5]) + 1;
	}
	// write 1-30
	for (int i = 1; i <= 30; i++) {
		int bitpos = (i - 1) / 5, bitval = (i - 1) % 5;
		ret[i][0] = 1;
		for (int j = 1; j <= n; j++) {
			int retval = j % go5[bitpos + 1] / go5[bitpos];
			if (bitval < retval) ret[i][j] = -1;
			else if (bitval > retval) ret[i][j] = -2;
			else ret[i][j] = 30 + bitpos;
		}
	}
	// write 31-35
	for (int i = 31; i <= 35; i++) {
		int bitpos = (i - 31);
		ret[i][0] = 0;
		for (int j = 1; j <= n; j++) {
			ret[i][j] = bitpos * 5 + (j % go5[bitpos + 1] / go5[bitpos]) + 1;
		}
	}
	return ret;
}

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