제출 #625800

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

prison

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

using namespace std;

vector<vector<int>> ans;
int n;

void fin(int p, int c, int l, int r, int pl, int pr, int b){
	for(int i = l; i <= r; ++i)ans[p][i] = 3*c+b;
	for(int i = pl; i<= l; ++i)ans[3*c+b][i] = ~ans[3*c+b][0];
	for(int i = r; i<= pr; ++i)ans[3*c+b][i] = ~(int)(!ans[3*c+b][0]);
	l++;
	r--;
	if(l > r)return;
	if(l+2 > r){
		fin(c*3+b, c+1, l   , r , l-1, r+1, 1);
		return;
	}
	if(l+4 > r){
		int m = (l+r)/2;
		fin(c*3+b, c+1, l   , m , l-1, r+1, 1);
		fin(c*3+b, c+1, m+1 , r , l-1, r+1, 2);
		return;
	}
	int d1 = (l+l+r)/3, d2 = (r+r+l)/3;
		fin(c*3+b, c+1, l   , d1, l-1, r+1, 1);
		fin(c*3+b, c+1, d1+1, d2, l-1, r+1, 2);
		fin(c*3+b, c+1, d2+1, r , l-1, r+1, 3);
}

vector<vector<int>> devise_strategy(int N) {
	n = N;
	ans.resize(21,vector<int>(N+1,0));
	for(int i = 0; i < 21; ++i)ans[i][0] = ((i+2)%6 < 3);
	fin(0,-1,1,N,1,N,3);
	return ans;
}

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