제출 #632279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
632279		kingmoshe	죄수들의 도전 (IOI22_prison)	C++17	0 / 100	5 ms	980 KiB

prison

#include "prison.h"

#include <vector>
//#include <iostream>
typedef std::pair<int, int> ii;
typedef std::vector<int> vi;
typedef std::vector<ii> vii;
typedef std::vector<vi> vvi;
typedef std::vector<vii> vvii;

vvi res(0, vi(0));
int maximal_number = 21;
int N = 5000;

vvii ranges(int n) {
	vvii res(0);
	res.push_back(vii{ ii(1, n) });
	for (int i = 0; i < 10; i++) {
		vii new_ranges(0);
		for (int j = 0; j < int(res[i].size()); j++) {
			int small = res[i][j].first;
			int large = res[i][j].second;
			small += 1;
			large -= 1;
			int mid = (small + large) / 2;
			new_ranges.push_back(ii(small, mid));
			new_ranges.push_back(ii(mid + 1, large));
		}
		res.push_back(new_ranges);
	}
	return res;
}

void init_res(int N) {
	res.resize(maximal_number + 1, vi(N + 1));
	for (int i = 0; i <= maximal_number; i++) {
		for (int j = 0; j <= N; j++) {
			res[i][j] = 0;
		}
	}
}
void set_res_bag_choice(int N) {
	for (int i = 0; i <= maximal_number; i++) {
		res[i][0] = 0;
	}
	for (int i = 0; i <= maximal_number; i++) {
		if (1 + i + i <= maximal_number) {
			res[1 + i + i][0] = 1;
		}
		if (2 + i + i <= maximal_number) {
			res[2 + i + i][0] = 1;
		}
	}
}
void set_0_number() {
	for (int i = 1; i <= 5000; i++) {
		int val = 0;
		if (i == 1) {
			val = -1;
		}
		else if (i == 5000) {
			val = -2;
		}
		else if (i <= 2500) {
			val = 1;
		}
		else {
			val = 2;
		}
		res[0][i] = val;
	}
}
void set_number(int number, vii possible_number_ranges) {
	bool last_is_smaller = (number % 2) == 1;
	bool last_was_a = ((number % 4) == 1) || ((number % 4 == 2));
	int im_smaller_indicator = -1;
	int im_bigger_indicator = -2;
	if (last_was_a) {
		im_smaller_indicator = -2;
		im_bigger_indicator = -1;
	}
	int next_value_small = 1 + number + (number % 2);
	int next_value_large = next_value_small + 1;
	for (int i = 0; i < int(possible_number_ranges.size()); i += 2) {
		ii smaller = possible_number_ranges[i];
		ii larger = possible_number_ranges[i + 1];
		res[number][smaller.first - 1] = im_smaller_indicator;
		res[number][smaller.first] = im_smaller_indicator;
		if (last_is_smaller) {
			res[number][smaller.second] = im_bigger_indicator;
		}
		else {
			res[number][smaller.second] = im_smaller_indicator;
		}
		res[number][larger.second + 1] = im_bigger_indicator;
		res[number][larger.second] = im_bigger_indicator;
		if (last_is_smaller) {
			res[number][larger.first] = im_bigger_indicator;
		}
		else {
			res[number][larger.first] = im_smaller_indicator;
		}
		for (int j = smaller.first + 1; j < smaller.second; j++) {
			res[number][j] = next_value_small;
			if (!last_is_smaller) {
				res[number][j] = im_smaller_indicator;
			}
		}
		for (int j = larger.first + 1; j < larger.second; j++) {
			res[number][j] = next_value_large;
			if (last_is_smaller) {
				res[number][j] = im_bigger_indicator;
			}
		}
	}
}
void set_last_number(int number, vii last_possible_number_ranges) {
	bool last_was_a = ((number % 4) == 1) || ((number % 4 == 2));
	int im_smaller_indicator = -1;
	int im_bigger_indicator = -2;
	if (last_was_a) {
		im_smaller_indicator = -2;
		im_bigger_indicator = -1;
	}
	for (int i = 0; i < int(last_possible_number_ranges.size()); i+= 2) {
		ii smaller = last_possible_number_ranges[i];
		ii larger = last_possible_number_ranges[i + 1];
		int first_diff = smaller.second - smaller.first;
		int second_diff = larger.second - larger.first;
		if (first_diff == 2 && second_diff == 2) {
			res[number][smaller.first] = im_smaller_indicator;
			res[number][smaller.second] = im_bigger_indicator;
			res[number][larger.first] = im_smaller_indicator;
			res[number][larger.second] = im_bigger_indicator;
		}
		else if (first_diff == 2 && second_diff == 1) {
			res[number][smaller.first] = im_smaller_indicator;
			res[number][smaller.second] = im_bigger_indicator;
		}
	}
}
vvi devise_strategy(int n) {
	vvii ranges_vec = ranges(N);
	init_res(N);
	set_res_bag_choice(N);
	set_0_number();
	int counter = 1;
	for (int i = 1; true; i++) {
		if ((i % 2 == 1) && i != 1) {
			counter += 1;
		}
		if (counter >= int(ranges_vec.size())) {
			break;
		}
		set_number(i, ranges_vec[counter]);
	}
	set_last_number(maximal_number, ranges_vec[int(ranges_vec.size()) - 1]);
	vvi result(maximal_number + 1, vi(n + 1));
	for (int i = 0; i <= maximal_number; i++) {
		result[i][0] = res[i][0];
		for (int j = 1; j <= n; j++) {
			result[i][j] = res[i][j];
			if (res[i][j] > maximal_number) {
				result[i][j] = maximal_number;
			}
			if (res[i][j] == 0) {
				result[i][j] = maximal_number;
			}
		}
	}
	return result;
}
/*int main() {
	vvi v = devise_strategy(5000);
	vvii vec = ranges(5000);
	vi diffs(10);
	return 0;
}*/

//number -> 
// looking at first_bag ->  (0,3,4,7,8,11,12,15,16,19,20
// looking at second_bag -> (1,2,5,6,9,10,13,14,17,18

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