Submission #632275

#	Time	Username	Problem	Language	Result	Execution time	Memory
632275		kingmoshe	Prisoner Challenge (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 < 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 < 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 < 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 >= ranges_vec.size()) {
			break;
		}
		set_number(i, ranges_vec[counter]);
	}
	set_last_number(maximal_number, ranges_vec[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

Compilation message (stderr)

prison.cpp: In function 'vvii ranges(int)':
prison.cpp:20:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for (int j = 0; j < res[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
prison.cpp: In function 'void set_number(int, vii)':
prison.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for (int i = 0; i < possible_number_ranges.size(); i += 2) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
prison.cpp: In function 'void set_last_number(int, vii)':
prison.cpp:125:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |  for (int i = 0; i < last_possible_number_ranges.size(); i+= 2) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
prison.cpp: In function 'vvi devise_strategy(int)':
prison.cpp:152:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |   if (counter >= ranges_vec.size()) {
      |       ~~~~~~~~^~~~~~~~~~~~~~~~~~~~

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