제출 #748696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748696		QwertyPi	죄수들의 도전 (IOI22_prison)	C++17	51.50 / 100	15 ms	1880 KiB

prison

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

using namespace std;

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

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

void solve(int L, int R, int ai, int ID){
	// cout << R - L << ' ' << ai << ' ' << ID << endl;
	if(ai == -1 || R - L < 2) return;
	
	ans[ID][L] = -1;
	ans[ID][R - 1] = -2;
	L++; R--;
	if(L >= R) 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[i]; j < M[i + 1]; j++){
			ans[ID][j] = ID + i + 1;
		}
		for(int j = L - 1; j <= M[i]; j++){
			ans[ID + i + 1][j] = -2;
		}
		for(int j = M[i] + 1; j < M[i + 1] - 1; j++){
			ans[ID + i + 1][j] = ID + a[ai] + 1;
		}
		for(int j = M[i + 1] - 1; j < R + 1; 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: 41.5 / 90