Submission #632321

#	Time	Username	Problem	Language	Result	Execution time	Memory
632321		kingmoshe	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	7 ms	1032 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 = 1; i <= maximal_number; i+=4) {
		res[i][0] = 1;
		if (i + 1 <= maximal_number) {
			res[i + 1][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];
		for (int j = smaller.first; j <= smaller.second; j++) {
			res[number][j] = next_value_small;
		}
		for (int j = larger.first; j <= larger.second; j++) {
			res[number][j] = next_value_large;
		}
	}
	if (int(possible_number_ranges.size()) == 2) {
		if (last_is_smaller) {
			for (int i = 2500; i <= 5000; i++) {
				res[number][i] = im_bigger_indicator;
			}
			res[number][1] = im_smaller_indicator;
			res[number][2] = im_smaller_indicator;
		}
		else {
			for (int i = 1; i <= 2501; i++) {
				res[number][i] = im_smaller_indicator;
			}
			res[number][5000] = im_bigger_indicator;
			res[number][4999] = im_bigger_indicator;
		}
		return;
	}
	if (last_is_smaller) {
		for (int i = 0; i < int(possible_number_ranges.size()); i += 4) {
			ii p1 = possible_number_ranges[i];
			ii p2 = possible_number_ranges[i + 1];
			ii p3 = possible_number_ranges[i + 2];
			ii p4 = possible_number_ranges[i + 3];

			int small_range = p3.first - 3;
			int larger_range = p4.second + 1;
			for (int j = small_range; j <= larger_range; j++) {
				res[number][j] = im_bigger_indicator;
			}
			res[number][p1.first] = im_smaller_indicator;
			res[number][p1.first - 1] = im_smaller_indicator;
		}
	}
	else {
		for (int i = 0; i < int(possible_number_ranges.size()); i += 4) {
			ii p1 = possible_number_ranges[i];
			ii p2 = possible_number_ranges[i + 1];
			ii p3 = possible_number_ranges[i + 2];
			ii p4 = possible_number_ranges[i + 3];
			int small_range = p1.first - 1;
			int larger_range = p2.second + 3;
			for (int j = small_range; j <= larger_range; j++) {
				res[number][j] = im_smaller_indicator;
			}
			res[number][p4.second] = im_bigger_indicator;
			res[number][p4.second + 1] = 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 get_result(int a, int b, vvi result) {
	int current_number = 0;
	while (true) {
		std::cout << "here " << current_number << std::endl;
		bool looking_at_a = false;
		if (result[current_number][0] == 0) {
			looking_at_a = true;
		}
		else if (result[current_number][0] == 1) {
			looking_at_a = false;
		}
		else {
			std::cout << "major problem" << std::endl;
		}
		int value = 0;
		if (looking_at_a) {
			value = a;
		}
		else {
			value = b;
		}
		if (result[current_number][value] == -1) {
			return -1;
		}
		else if (result[current_number][value] == -2) {
			return -2;
		}
		else {
			current_number = result[current_number][value];
		}
	}
}
/*int main() {
	vvi v = devise_strategy(243);
	std::cout << get_result(161, 7, v) << std::endl;
	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

Compilation message (stderr)

prison.cpp: In function 'void set_number(int, vii)':
prison.cpp:112:7: warning: variable 'p2' set but not used [-Wunused-but-set-variable]
  112 |    ii p2 = possible_number_ranges[i + 1];
      |       ^~
prison.cpp:129:7: warning: variable 'p3' set but not used [-Wunused-but-set-variable]
  129 |    ii p3 = possible_number_ranges[i + 2];
      |       ^~

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