제출 #987337

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

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
int dvd[7] = {3, 3, 3, 3, 3, 3, 2};
int cdiv(int a, int b){
	return (a + b - 1) / b;
}
tuple<int, int, int> split(int l, int r, int v, int did){
	if (v == l) return {-1, -1, -1};
	else if (v == r) return {-1, -1, 5};
	l++; r--;
	int gsz = cdiv(r - l + 1, dvd[did]), gid = (v - l) / gsz;
	l = l + gsz * gid; 
	r = min(r, l + gsz - 1);
	return {l, r, gid};
}
tuple<int, int, int> getr(int dv, int v){
	int l = 1, r = 5000, gid = -1;
	for (int i = 0; i < dv; i++){
		tie(l, r, gid) = split(l, r, v, i);
		if (l == -1) break;
	}
	return {l, r, gid};
}
vector<vector<int>> devise_strategy(int N){
	vector<vector<int>> ret(21, vector<int>(N + 1, 0));
	ret[0][0] = 0;
	for (int v = 1; v <= N; v++){
		if (v == 1) ret[0][v] = -1; 
		else if (v == 5000) ret[0][v] = -2;
		else ret[0][v] = 1 + get<2>(split(1, 5000, v, 0));
	}
	for (int i = 1; i < 21; i++){
		int dv = (i + 2) / 3, mod = (i + 2) % 3;
		ret[i][0] = dv & 1;
		for (int v = 1; v <= N; v++){
			int l, r, gid; tie(l, r, gid) = getr(dv, v);
			if (gid < mod) ret[i][v] = -(ret[i][0] + 1);
			else if (gid > mod) ret[i][v] = -(2 - ret[i][0]);
			else if (v == l) ret[i][v] = -(ret[i][0] + 1);
			else if (v == r) ret[i][v] = -(2 - ret[i][0]);
			else if (dv < 8) ret[i][v] = dv * 3 + 1 + get<2>(split(l, r, v, dv));
		}
	}
	return ret;
}

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