Submission #748678

#	Time	Username	Problem	Language	Result	Execution time	Memory
748678		QwertyPi	Prisoner Challenge (IOI22_prison)	C++17	47 / 100	21 ms	2004 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

const int MAGIC = 33;
vector<vector<int>> ans;

int a[8] = {3, 3, 3, 3, 3, 3, 3, 3};

void solve(int L, int R, int ai, int ID){
	if(ai == -1) return;
	vector<int> M;
	M.push_back(L);
	for(int i = 1; i < a[ai]; i++){
		M.push_back((L * (a[ai] - i) + R * i) / a[ai]);
	}
	M.push_back(R);
	ans[ID][0] = 0;
	for(int i = 0; i < a[ai]; i++){
		ans[ID + i + 1][0] = 1;
	}
	
	for(int i = 0; i < a[ai]; i++){
		for(int j = M[0]; j < M[i]; j++){
			ans[ID + i + 1][j] = -2;
		}
		for(int j = M[i]; j < M[i + 1]; j++){
			ans[ID][j] = ID + i + 1;
			ans[ID + i + 1][j] = ID + a[ai] + 1;
		}
		for(int j = M[i + 1]; j < M[a[ai]]; j++){
			ans[ID + i + 1][j] = -1;
		}
	}
	
	for(int i = 0; i < a[ai]; i++){
		solve(M[i], M[i + 1], ai - 1, ID + a[ai] + 1);
	}
}

vector<vector<int>> devise_strategy(int N) {
	ans = vector<vector<int>>(MAGIC, vector<int>(N + 1));
	solve(1, N + 1, 7, 0);
	return ans;
}

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