Submission #1171229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171229		thelegendary08	죄수들의 도전 (IOI22_prison)	C++17	0 / 100	1 ms	324 KiB

prison

#include "prison.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vout(x) for(auto u : x)cout<<u<<' ';cout<<'\n';
using namespace std;
const vi divv = {3,3,3,3,3,2,2,1};
const vi ad = {1,4,7,10,13,16,19,20};
const vi chec = {0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,1,1,0};
vector<vi>v(21);
void solve(int l, int r, int layer, int dex){
	if(divv[layer] == 3){
		for(int j = ad[layer]; j<=ad[layer] + 2; j++){
			if(j > dex){
				for(int i = l; i<=r; i++){
					if(layer % 2 == 0){
						v[j][i] = -2;
					}
					else v[j][i] = -1;
				}
			}
			else if(j < dex){
				for(int i = l; i<=r; i++){
					if(layer % 2 == 0){
						v[j][i] = -1;
					}
					else v[j][i] = -2;
				}
			}
			else{
				if(divv[layer + 1] == 3){
					int a = l + (r - l + 1) / 3;
					int b = l + (r - l + 1) / 3 * 2;
					for(int i = l; i<=r; i++){
						if(i < a)v[j][i] = ad[layer + 1];
						else if(i < b)v[j][i] = ad[layer + 1] + 1;
						else v[j][i] = ad[layer + 1] + 2;
					}
					if(layer % 2 == 0){
						v[j][l] = -2;
						v[j][a-1] = -1;
						v[j][a] = -2;
						v[j][b-1] = -1;
						v[j][b] = -2;
						v[j][r] = -1;
					}
					else{
						v[j][l] = -1;
						v[j][a-1] = -2;
						v[j][a] = -1;
						v[j][b-1] = -2;
						v[j][b] = -1;
						v[j][r] = -2;
					}
					
					solve(l+1, a-2, layer + 1, ad[layer + 1]);
					solve(a+1, b-2, layer + 1, ad[layer + 1] + 1);
					solve(b+1, r-1, layer + 1, ad[layer + 1] + 2);
				}
				else{
					int mid = (l + r) / 2;
					for(int i = l; i<=r; i++){
						if(i <= mid)v[j][i] = ad[layer + 1];
						else v[j][i] = ad[layer + 1] + 1;
					}
					if(layer % 2 == 0){
						v[j][l] = -2;
						v[j][mid] = -1;
						v[j][mid + 1] = -2;
						v[j][r] = -1;
					}
					else{
						v[j][l] = -1;
						v[j][mid] = -2;
						v[j][mid + 1] = -1;
						v[j][r] = -2;
					}
					solve(l, mid, layer + 1, ad[layer + 1]);
					solve(mid + 1, r, layer + 1, ad[layer + 1] + 1);
				}
			}
		}
	}
	else if(divv[layer] == 2){
		for(int j = ad[layer]; j<=ad[layer] + 1; j++){
			if(j > dex){
				for(int i = l; i<=r; i++){
					if(layer % 2 == 0){
						v[j][i] = -2;
					}
					else v[j][i] = -1;
				}
			}
			else if(j < dex){
				for(int i = l; i<=r; i++){
					if(layer % 2 == 0){
						v[j][i] = -1;
					}
					else v[j][i] = -2;
				}
			}
			else{
				if(divv[layer + 1] == 1){
					for(int i = l; i<=r; i++){
						v[j][i] = ad[layer + 1];
					}
					if(layer % 2 == 0){
						v[j][l] = -2;
						v[j][r] = -1;
					}
					else{
						v[j][l] = -1;
						v[j][r] = -2;
					}
					solve(l + 1, r - 1, layer + 1, ad[layer + 1]);
				}
				else{
					int mid = (l + r) / 2;
					for(int i = l; i<=r; i++){
						if(i <= mid)v[j][i] = ad[layer + 1];
						else v[j][i] = ad[layer + 1] + 1;
					}
					if(layer % 2 == 0){
						v[j][l] = -2;
						v[j][mid] = -1;
						v[j][mid + 1] = -2;
						v[j][r] = -1;
					}
					else{
						v[j][l] = -1;
						v[j][mid] = -2;
						v[j][mid + 1] = -1;
						v[j][r] = -2;
					}
					solve(l, mid, layer + 1, ad[layer + 1]);
					solve(mid + 1, r, layer + 1, ad[layer + 1] + 1);
				}
			}
		}
	}
	else{
		if(l != r){
			if(layer % 2 == 0){
				v[dex][l] = -2;
				v[dex][r] = -1;
			}
			else{
				v[dex][l] = -1;
				v[dex][r] = -2;
			}
		}
	}
}
std::vector<std::vector<int>> devise_strategy(int N) {
	f0r(i, 21)v[i].resize(N+1);
	f0r(i, 21)v[i][0] = chec[i];
	int a = N / 3;
	int b = N / 3 * 2;
	FOR(i, 1, N+1){
		if(i < a)v[0][i] = 1;
		else if(i < b)v[0][i] = 2;
		else v[0][i] = 3;	
	}
	solve(1, a-1, 0, 1);
	solve(a, b-1, 0, 2);
	solve(b, N, 0, 3);
	return v;
	
}

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