Submission #987305

#	Time	Username	Problem	Language	Result	Execution time	Memory
987305		siewjh	Prisoner Challenge (IOI22_prison)	C++17	65 / 100	13 ms	1116 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
int p3[8];
int cdiv(int a, int b){
	return (a + b - 1) / b;
}
tuple<int, int, int> split(int l, int r, int v){
	int gsz = cdiv(r - l + 1, 3), 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);
	return {l, r, gid};
}
vector<vector<int>> devise_strategy(int N){
	vector<vector<int>> ret(25, vector<int>(N + 1, 0));
	ret[0][0] = 0;
	for (int v = 1; v <= N; v++) ret[0][v] = 1 + get<2>(split(1, 5000, v));
	for (int i = 1; i < 25; 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 (dv < 8) ret[i][v] = dv * 3 + 1 + get<2>(split(l, r, v));
		}
	}
	return ret;
}

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