#define INFOARENA_DTCSU__SOLVER__BULWARK__OPEN {
#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>
#include <stdbool.h>
#include <string.h>
#define INFOARENA_DTCSU__SOLVER__CONSTANTS__INPUT_FILE_ITS_FILE_PATH "dtcsu.in"
#define INFOARENA_DTCSU__SOLVER__CONSTANTS__OUTPUT_FILE_ITS_FILE_PATH "dtcsu.out"
#define INFOARENA_DTCSU__SOLVER__CONSTANTS__GIVEN_SET_ITS_SIZE 276997
#define INFOARENA_DTCSU__SOLVER__CONSTANTS__PRIME_ITSELF 277003
#define INFOARENA_DTCSU__SOLVER__CONSTANTS__COEFFICIENT_C0 708 /* c₀ */
#define INFOARENA_DTCSU__SOLVER__CONSTANTS__COEFFICIENT_C1 95703 /* c₁ */
#define INFOARENA_DTCSU__SOLVER__CONSTANTS__COEFFICIENT_C2 188687 /* c₂ */
#define INFOARENA_DTCSU__SOLVER__CONSTANTS__COEFFICIENT_C3 74877 /* c₃ */
#define INFOARENA_DTCSU__SOLVER__CONSTANTS__BOUND_ABOVE UINT64_C(1000000000000000000) /* 10¹⁸ */
#define INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE 0
#define INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__WEE_SIZE_TYPE 1
#define INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY 2
#define INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM 3
#define INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__OUTPUT_ERROR 4
#define INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INPUT_ERROR 5
#define INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INVALID_INPUT 6
#define INFOARENA_DTCSU__SOLVER__BULWARK__CLOSE }
struct infoarena_dtcsu__solver__data_up__program_state {
uint8_t * infoarena_dtcsu__solver__field__bucket_size_array_itself;
size_t infoarena_dtcsu__solver__field__bucket_size_array_its_size;
size_t * infoarena_dtcsu__solver__field__bucket_count_array_itself;
size_t infoarena_dtcsu__solver__field__bucket_count_array_its_size;
uint32_t * infoarena_dtcsu__solver__field__bucket_begin_array_itself;
size_t infoarena_dtcsu__solver__field__bucket_begin_array_its_size;
uint64_t * infoarena_dtcsu__solver__field__given_set_itself;
size_t infoarena_dtcsu__solver__field__given_set_its_size;
char * infoarena_dtcsu__solver__field__input_buffer_itself;
size_t infoarena_dtcsu__solver__field__input_buffer_its_size;
FILE * infoarena_dtcsu__solver__field__input_file_itself;
FILE * infoarena_dtcsu__solver__field__output_file_itself;
uint32_t infoarena_dtcsu__solver__field__answer_itself;
};
uint64_t hash_function_itself (uint64_t value_itself) {
/*
* https://www.youtube.com/watch?v=ggCu8rReKjk&list=PLEAYkSg4uSQ37A6_NrUnTHEKp6EkAxTMa&index=76
*
* 15 2 Universal Hashing Definition and Example Advanced Optional 26 min
*
* Stanford Algorithms. (Tim Roughgarden)
*
*
* https://www.cs.cmu.edu/~avrim/451f11/lectures/lect1004.pdf (it gives an idea on how to build a perfect hash function, quite neat!)
*
* Initial idea: build a perfect hash; dropped, 5120 kbytes memory limit would have been exceeded.
*
* Trade off: maybe a hash table with at most 7 collisions per bucket would be good enough, and this is the approach in this file.
*
*
* The hash function was simply found during a Bernoulli trial, when the objective still was to build the perfect hash.
*/
return ( ( (((value_itself >> 0) & 0xffff) * ((uint64_t) INFOARENA_DTCSU__SOLVER__CONSTANTS__COEFFICIENT_C0)) +
(((value_itself >> 16) & 0xffff) * ((uint64_t) INFOARENA_DTCSU__SOLVER__CONSTANTS__COEFFICIENT_C1)) +
(((value_itself >> 32) & 0xffff) * ((uint64_t) INFOARENA_DTCSU__SOLVER__CONSTANTS__COEFFICIENT_C2)) +
(((value_itself >> 48) & 0xffff) * ((uint64_t) INFOARENA_DTCSU__SOLVER__CONSTANTS__COEFFICIENT_C3)) ) %
INFOARENA_DTCSU__SOLVER__CONSTANTS__PRIME_ITSELF );
}
int read_a_number (FILE * input_file_itself, char * buffer_itself, size_t buffer_its_size, size_t * buffer_its_index_ptr, uint64_t * value_itself_ptr) {
int exit_status_itself = 0;
size_t buffer_its_index = 0;
uint64_t value_itself = 0;
size_t status_of_sorts = 0;
char ch = '\0';
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
buffer_its_index = *buffer_its_index_ptr;
do {
if (buffer_its_index == buffer_its_size) {
(void) memset(buffer_itself, 0, buffer_its_size);
status_of_sorts = fread(buffer_itself, 1, buffer_its_size, input_file_itself);
if (0 == status_of_sorts) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INPUT_ERROR;
}
else {
buffer_its_index = 1;
ch = buffer_itself[0];
}
}
else {
ch = buffer_itself[buffer_its_index];
buffer_its_index += 1;
}
}
while ((INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) && ( ! ('0' <= ch) && (ch <= '9') ));
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
value_itself = 0;
do {
value_itself = value_itself * 10 + ((uint64_t) (ch - '0'));
if (buffer_its_index == buffer_its_size) {
(void) memset(buffer_itself, 0, buffer_its_size);
status_of_sorts = fread(buffer_itself, 1, buffer_its_size, input_file_itself);
if (0 == status_of_sorts) {
ch = '\0';
buffer_its_index = buffer_its_size;
}
else {
buffer_its_index = 1;
ch = buffer_itself[0];
}
}
else {
ch = buffer_itself[buffer_its_index];
buffer_its_index += 1;
}
}
while ((INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) && (('0' <= ch) && (ch <= '9')));
}
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
*buffer_its_index_ptr = buffer_its_index;
*value_itself_ptr = value_itself;
}
return exit_status_itself;
}
int infoarena_dtcsu__solver__code_up__acquire_all_resources_up_front (struct infoarena_dtcsu__solver__data_up__program_state * * program_state_its_receptacle) {
/* Step is declare and define locals. */ {
INFOARENA_DTCSU__SOLVER__BULWARK__CLOSE
int exit_status_itself = 0;
struct infoarena_dtcsu__solver__data_up__program_state * program_state_itself = NULL;
uint8_t * bucket_size_array_itself = NULL;
size_t bucket_size_array_its_size = 0;
size_t * bucket_count_array_itself = NULL;
size_t bucket_count_array_its_size = 0;
uint32_t * bucket_begin_array_itself = NULL;
size_t bucket_begin_array_its_size = 0;
uint64_t * given_set_itself = NULL;
size_t given_set_its_size = 0;
char * input_buffer_itself = 0;
size_t input_buffer_its_size = 0;
FILE * input_file_itself = NULL;
FILE * output_file_itself = NULL;
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
INFOARENA_DTCSU__SOLVER__BULWARK__OPEN
}
/* Step is verify the adequacy of size type, one warming up and incipient question. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
if (SIZE_MAX < INFOARENA_DTCSU__SOLVER__CONSTANTS__GIVEN_SET_ITS_SIZE) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__WEE_SIZE_TYPE;
}
}
}
/* Step is malloc() acquire the program state itself, the basket of cornucopia. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
size_t number_of_bytes = 0;
void * pointer_itself = NULL;
number_of_bytes = sizeof(struct infoarena_dtcsu__solver__data_up__program_state);
pointer_itself = malloc(number_of_bytes);
if (NULL == pointer_itself) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY;
}
else {
program_state_itself = pointer_itself;
}
}
}
/* Step is malloc() acquire the bucket size array itself. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
size_t number_of_elements = 0;
size_t element_byte_size = 0;
size_t number_of_bytes = 0;
void * pointer_itself = NULL;
number_of_elements = INFOARENA_DTCSU__SOLVER__CONSTANTS__PRIME_ITSELF;
element_byte_size = sizeof(uint8_t);
if ((SIZE_MAX / element_byte_size) < number_of_elements) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__WEE_SIZE_TYPE;
}
else {
number_of_bytes = number_of_elements * element_byte_size;
pointer_itself = malloc(number_of_bytes);
if (NULL == pointer_itself) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY;
}
else {
bucket_size_array_itself = pointer_itself;
bucket_size_array_its_size = number_of_elements;
}
}
}
}
/* Step is malloc() acquire the bucket count array itself. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
size_t number_of_elements = 0;
size_t element_byte_size = 0;
size_t number_of_bytes = 0;
void * pointer_itself = NULL;
number_of_elements = 16;
element_byte_size = sizeof(size_t);
if ((SIZE_MAX / element_byte_size) < number_of_elements) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__WEE_SIZE_TYPE;
}
else {
number_of_bytes = number_of_elements * element_byte_size;
pointer_itself = malloc(number_of_bytes);
if (NULL == pointer_itself) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY;
}
else {
bucket_count_array_itself = pointer_itself;
bucket_count_array_its_size = number_of_elements;
}
}
}
}
/* Step is malloc() acquire the bucket begin array itself. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
size_t number_of_elements = 0;
size_t element_byte_size = 0;
size_t number_of_bytes = 0;
void * pointer_itself = NULL;
number_of_elements = INFOARENA_DTCSU__SOLVER__CONSTANTS__PRIME_ITSELF + 1;
element_byte_size = sizeof(uint32_t);
if ((SIZE_MAX / element_byte_size) < number_of_elements) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__WEE_SIZE_TYPE;
}
else {
number_of_bytes = number_of_elements * element_byte_size;
pointer_itself = malloc(number_of_bytes);
if (NULL == pointer_itself) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY;
}
else {
bucket_begin_array_itself = pointer_itself;
bucket_begin_array_its_size = number_of_elements;
}
}
}
}
/* Step is malloc() acquire the given set its backing array with values increasing by bucket. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
size_t number_of_elements = 0;
size_t element_byte_size = 0;
size_t number_of_bytes = 0;
void * pointer_itself = NULL;
number_of_elements = INFOARENA_DTCSU__SOLVER__CONSTANTS__GIVEN_SET_ITS_SIZE;
element_byte_size = sizeof(uint64_t);
if ((SIZE_MAX / element_byte_size) < number_of_elements) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__WEE_SIZE_TYPE;
}
else {
number_of_bytes = number_of_elements * element_byte_size;
pointer_itself = malloc(number_of_bytes);
if (NULL == pointer_itself) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY;
}
else {
given_set_itself = pointer_itself;
given_set_its_size = number_of_elements;
}
}
}
}
/* Step is malloc() acquire the input buffer itself. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
size_t number_of_elements = 0;
size_t element_byte_size = 0;
size_t number_of_bytes = 0;
void * pointer_itself = NULL;
number_of_elements = 32768;
element_byte_size = sizeof(char);
if ((SIZE_MAX / element_byte_size) < number_of_elements) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__WEE_SIZE_TYPE;
}
else {
number_of_bytes = number_of_elements * element_byte_size;
pointer_itself = malloc(number_of_bytes);
if (NULL == pointer_itself) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY;
}
else {
input_buffer_itself = pointer_itself;
input_buffer_its_size = number_of_elements;
}
}
}
}
/* Step is fopen() acquire the input file itself. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
char * file_path = NULL;
FILE * pointer_itself = NULL;
file_path = INFOARENA_DTCSU__SOLVER__CONSTANTS__INPUT_FILE_ITS_FILE_PATH;
pointer_itself = fopen(file_path, "r");
if (NULL == pointer_itself) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INPUT_ERROR;
}
else {
input_file_itself = pointer_itself;
}
}
}
/* Step is fopen() acquire the output file itself. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
char * file_path = NULL;
FILE * pointer_itself = NULL;
file_path = INFOARENA_DTCSU__SOLVER__CONSTANTS__OUTPUT_FILE_ITS_FILE_PATH;
pointer_itself = fopen(file_path, "w");
if (NULL == pointer_itself) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INPUT_ERROR;
}
else {
output_file_itself = pointer_itself;
}
}
}
/* Step is pass the baton, and the caller is to carry on, with it. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
program_state_itself->infoarena_dtcsu__solver__field__bucket_size_array_itself = bucket_size_array_itself;
program_state_itself->infoarena_dtcsu__solver__field__bucket_size_array_its_size = bucket_size_array_its_size;
program_state_itself->infoarena_dtcsu__solver__field__bucket_count_array_itself = bucket_count_array_itself;
program_state_itself->infoarena_dtcsu__solver__field__bucket_count_array_its_size = bucket_count_array_its_size;
program_state_itself->infoarena_dtcsu__solver__field__bucket_begin_array_itself = bucket_begin_array_itself;
program_state_itself->infoarena_dtcsu__solver__field__bucket_begin_array_its_size = bucket_begin_array_its_size;
program_state_itself->infoarena_dtcsu__solver__field__given_set_itself = given_set_itself;
program_state_itself->infoarena_dtcsu__solver__field__given_set_its_size = given_set_its_size;
program_state_itself->infoarena_dtcsu__solver__field__input_buffer_itself = input_buffer_itself;
program_state_itself->infoarena_dtcsu__solver__field__input_buffer_its_size = input_buffer_its_size;
program_state_itself->infoarena_dtcsu__solver__field__input_file_itself = input_file_itself;
program_state_itself->infoarena_dtcsu__solver__field__output_file_itself = output_file_itself;
program_state_itself->infoarena_dtcsu__solver__field__answer_itself = 0;
*program_state_its_receptacle = program_state_itself;
}
else {
if (NULL != input_file_itself) {
int status_of_sorts = 0;
status_of_sorts = fclose(input_file_itself);
input_file_itself = NULL;
(void) status_of_sorts;
}
if (NULL != input_buffer_itself) {
free(program_state_itself->infoarena_dtcsu__solver__field__input_buffer_itself);
program_state_itself->infoarena_dtcsu__solver__field__input_buffer_itself = NULL;
program_state_itself->infoarena_dtcsu__solver__field__input_buffer_its_size = 0;
}
if (NULL != given_set_itself) {
free(program_state_itself->infoarena_dtcsu__solver__field__given_set_itself);
program_state_itself->infoarena_dtcsu__solver__field__given_set_itself = NULL;
program_state_itself->infoarena_dtcsu__solver__field__given_set_its_size = 0;
}
if (NULL != bucket_begin_array_itself) {
free(bucket_begin_array_itself);
bucket_begin_array_itself = NULL;
bucket_begin_array_its_size = 0;
}
if (NULL != bucket_count_array_itself) {
free(bucket_count_array_itself);
bucket_count_array_itself = NULL;
bucket_count_array_its_size = 0;
}
if (NULL != bucket_size_array_itself) {
free(bucket_size_array_itself);
bucket_size_array_itself = NULL;
bucket_size_array_its_size = 0;
}
if (NULL != program_state_itself) {
free(program_state_itself);
program_state_itself = NULL;
}
}
return exit_status_itself;
}
}
int infoarena_dtcsu__solver__code_up__build_the_hash_table_already (struct infoarena_dtcsu__solver__data_up__program_state * program_state_itself) {
/* Step is introduce local variables. */ {
INFOARENA_DTCSU__SOLVER__BULWARK__CLOSE
int exit_status_itself = 0;
uint8_t * bucket_size_array_itself = NULL;
size_t bucket_size_array_its_size = 0;
size_t * bucket_count_array_itself = NULL;
size_t bucket_count_array_its_size = 0;
uint32_t * bucket_begin_array_itself = NULL;
size_t bucket_begin_array_its_size = 0;
uint64_t * given_set_itself = NULL;
size_t given_set_its_size = 0;
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
bucket_size_array_itself = program_state_itself->infoarena_dtcsu__solver__field__bucket_size_array_itself;
bucket_size_array_its_size = program_state_itself->infoarena_dtcsu__solver__field__bucket_size_array_its_size;
bucket_count_array_itself = program_state_itself->infoarena_dtcsu__solver__field__bucket_count_array_itself;
bucket_count_array_its_size = program_state_itself->infoarena_dtcsu__solver__field__bucket_count_array_its_size;
bucket_begin_array_itself = program_state_itself->infoarena_dtcsu__solver__field__bucket_begin_array_itself;
bucket_begin_array_its_size = program_state_itself->infoarena_dtcsu__solver__field__bucket_begin_array_its_size;
given_set_itself = program_state_itself->infoarena_dtcsu__solver__field__given_set_itself;
given_set_its_size = program_state_itself->infoarena_dtcsu__solver__field__given_set_its_size;
INFOARENA_DTCSU__SOLVER__BULWARK__OPEN
}
/* Step is validate bucket count array, the size be at least 8 or more. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
if (bucket_count_array_its_size < 8) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
}
}
/* Step is make sure the nested loops over the elements of S would be fine, uint64 wrap around would not be possible. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
if ((UINT64_MAX / 11) < INFOARENA_DTCSU__SOLVER__CONSTANTS__BOUND_ABOVE) {
/* Look before you leap.
*
* Look before you loop.
*/
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__WEE_SIZE_TYPE;
}
}
}
/* Step is one pass over the bucket size array, memset() zero, compiler is invited to optimize! */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
size_t index_itself = 0;
index_itself = 0;
while (index_itself < bucket_size_array_its_size) {
bucket_size_array_itself[index_itself] = 0;
index_itself += 1;
}
}
}
/* Step is one pass over the given set S, hash and increment, hash and increment, updating bucket sizes. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
size_t current_size = 0;
size_t image_itself = 0;
/* Lots of maths, makes your head spin! */
for (uint64_t product_of_one_factor = 1; product_of_one_factor <= INFOARENA_DTCSU__SOLVER__CONSTANTS__BOUND_ABOVE; product_of_one_factor *= 11) {
for (uint64_t product_of_two_factors = product_of_one_factor; product_of_two_factors <= INFOARENA_DTCSU__SOLVER__CONSTANTS__BOUND_ABOVE; product_of_two_factors *= 7) {
for (uint64_t product_of_three_factors = product_of_two_factors; product_of_three_factors <= INFOARENA_DTCSU__SOLVER__CONSTANTS__BOUND_ABOVE; product_of_three_factors *= 5) {
for (uint64_t product_of_four_factors = product_of_three_factors; product_of_four_factors <= INFOARENA_DTCSU__SOLVER__CONSTANTS__BOUND_ABOVE; product_of_four_factors *= 3) {
for (uint64_t product_of_five_factors = product_of_four_factors; product_of_five_factors <= INFOARENA_DTCSU__SOLVER__CONSTANTS__BOUND_ABOVE; product_of_five_factors *= 2) {
if (current_size < INFOARENA_DTCSU__SOLVER__CONSTANTS__GIVEN_SET_ITS_SIZE) {
/* five factors, formally, or “in principle” */
image_itself = hash_function_itself(/* value_itself: */ product_of_five_factors);
bucket_size_array_itself[image_itself] += 1;
current_size += 1;
}
else {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
/* goto label_one; */ }}}}}}
/* label_one: */
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
if (INFOARENA_DTCSU__SOLVER__CONSTANTS__GIVEN_SET_ITS_SIZE != current_size) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
}
}
}
/* Step is one pass over the bucket size array, verify no wrap around has happened. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
size_t total = 0;
size_t index_itself = 0;
size_t value_itself = 0;
total = 0;
index_itself = 0;
while (index_itself < bucket_size_array_its_size) {
value_itself = bucket_size_array_itself[index_itself];
total += value_itself;
index_itself += 1;
}
if (INFOARENA_DTCSU__SOLVER__CONSTANTS__GIVEN_SET_ITS_SIZE != total) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
}
}
/* Step is one pass over the bucket size count array, memset() zero, compiler, you are invited to optimize! */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
size_t index_itself = 0;
index_itself = 0;
while (index_itself < bucket_count_array_its_size) {
bucket_count_array_itself[index_itself] = 0;
index_itself += 1;
}
}
}
/* Step is one pass over the buckets, to count these by their size. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
size_t index_itself = 0;
size_t value_itself = 0;
index_itself = 0;
while (index_itself < bucket_size_array_its_size) {
value_itself = bucket_size_array_itself[index_itself];
if (value_itself < (bucket_count_array_its_size - 1)) {
bucket_count_array_itself[value_itself] += 1;
}
else {
bucket_count_array_itself[bucket_count_array_its_size - 1] += 1;
}
index_itself += 1;
}
}
}
/* Step is verify buckets count give at most 7 elements of S in any bucket. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
size_t index_itself = 0;
size_t value_itself = 0;
index_itself = 8;
while ((INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) && (index_itself < bucket_count_array_its_size)) {
value_itself = bucket_count_array_itself[index_itself];
if (0 < value_itself) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
else {
index_itself += 1;
}
}
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
if (bucket_count_array_its_size <= 8) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
}
}
}
/* Step is verify bucket counts give expected results, a safety measure, while changing the program. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
/* 0:101613 1:102192 2:51114 3:16919 4:4159 5:862 6:134 7:10 0 0 0 0 0 0 0 0 */
if ((16 != bucket_count_array_its_size) ||
(101613 != bucket_count_array_itself[0]) ||
(102192 != bucket_count_array_itself[1]) ||
( 51114 != bucket_count_array_itself[2]) ||
( 16919 != bucket_count_array_itself[3]) ||
( 4159 != bucket_count_array_itself[4]) ||
( 862 != bucket_count_array_itself[5]) ||
( 134 != bucket_count_array_itself[6]) ||
( 10 != bucket_count_array_itself[7]) ||
( 0 != bucket_count_array_itself[8]) ||
( 0 != bucket_count_array_itself[9]) ||
( 0 != bucket_count_array_itself[10]) ||
( 0 != bucket_count_array_itself[11]) ||
( 0 != bucket_count_array_itself[12]) ||
( 0 != bucket_count_array_itself[13]) ||
( 0 != bucket_count_array_itself[14]) ||
( 0 != bucket_count_array_itself[15]) ) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
}
}
/* Step is accumulate the begin positions, bucket by bucket, scanning buckets increasing by their index or rank. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
size_t index_itself = 0;
size_t begin_itself = 0;
uint8_t size_itself = 0;
index_itself = 0;
index_itself = 0;
while (index_itself < bucket_size_array_its_size) {
bucket_begin_array_itself[index_itself] = begin_itself;
size_itself = bucket_size_array_itself[index_itself];
begin_itself += size_itself;
index_itself += 1;
}
bucket_begin_array_itself[bucket_size_array_its_size] = begin_itself;
}
}
/* Step is lay out elements of S, in increasing order by their hash value, the begin array would do its part. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
size_t current_size = 0;
size_t image_itself = 0;
/* Lots of maths, makes your head spin! */
for (uint64_t product_of_one_factor = 1; product_of_one_factor <= INFOARENA_DTCSU__SOLVER__CONSTANTS__BOUND_ABOVE; product_of_one_factor *= 11) {
for (uint64_t product_of_two_factors = product_of_one_factor; product_of_two_factors <= INFOARENA_DTCSU__SOLVER__CONSTANTS__BOUND_ABOVE; product_of_two_factors *= 7) {
for (uint64_t product_of_three_factors = product_of_two_factors; product_of_three_factors <= INFOARENA_DTCSU__SOLVER__CONSTANTS__BOUND_ABOVE; product_of_three_factors *= 5) {
for (uint64_t product_of_four_factors = product_of_three_factors; product_of_four_factors <= INFOARENA_DTCSU__SOLVER__CONSTANTS__BOUND_ABOVE; product_of_four_factors *= 3) {
for (uint64_t product_of_five_factors = product_of_four_factors; product_of_five_factors <= INFOARENA_DTCSU__SOLVER__CONSTANTS__BOUND_ABOVE; product_of_five_factors *= 2) {
if (current_size < INFOARENA_DTCSU__SOLVER__CONSTANTS__GIVEN_SET_ITS_SIZE) {
/* five factors, formally, or “in principle” */
image_itself = hash_function_itself(/* value_itself: */ product_of_five_factors);
given_set_itself[bucket_begin_array_itself[image_itself]] = product_of_five_factors;
bucket_begin_array_itself[image_itself] += 1;
current_size += 1;
}
else {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
/* goto label_one; */ }}}}}}
/* label_one: */
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
if (INFOARENA_DTCSU__SOLVER__CONSTANTS__GIVEN_SET_ITS_SIZE != current_size) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
else {
given_set_its_size = current_size;
(void) given_set_its_size;
}
}
}
}
/* Step is accumulate the begin positions, bucket by bucket, begin array is recomputed, and this is alright. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
if ((bucket_begin_array_its_size <= bucket_size_array_its_size) || ((bucket_begin_array_its_size - 1) != bucket_size_array_its_size)) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
else {
size_t index_itself = 0;
size_t begin_itself = 0;
uint8_t size_itself = 0;
index_itself = 0;
index_itself = 0;
while (index_itself < bucket_size_array_its_size) {
bucket_begin_array_itself[index_itself] = begin_itself;
size_itself = bucket_size_array_itself[index_itself];
begin_itself += size_itself;
index_itself += 1;
}
bucket_begin_array_itself[bucket_size_array_its_size] = begin_itself;
}
}
}
/* Step is pass the baton. */ {
return exit_status_itself;
}
}
int infoarena_dtcsu__solver__code_up__read_input_solve_all_queries (struct infoarena_dtcsu__solver__data_up__program_state * program_state_itself) {
/* Step is introduce local variables. */ {
INFOARENA_DTCSU__SOLVER__BULWARK__CLOSE
int exit_status_itself = 0;
uint32_t * bucket_begin_array_itself = NULL;
uint64_t * given_set_itself = NULL;
size_t given_set_its_size = 0;
char * input_buffer_itself = NULL;
size_t input_buffer_its_size = 0;
size_t input_buffer_its_index = 0;
FILE * input_file_itself = NULL;
uint32_t number_of_queries_itself = 0;
uint32_t answer_itself = 0;
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
bucket_begin_array_itself = program_state_itself->infoarena_dtcsu__solver__field__bucket_begin_array_itself;
given_set_itself = program_state_itself->infoarena_dtcsu__solver__field__given_set_itself;
given_set_its_size = program_state_itself->infoarena_dtcsu__solver__field__given_set_its_size;
input_buffer_itself = program_state_itself->infoarena_dtcsu__solver__field__input_buffer_itself;
input_buffer_its_size = program_state_itself->infoarena_dtcsu__solver__field__input_buffer_its_size;
input_buffer_its_index = input_buffer_its_size;
input_file_itself = program_state_itself->infoarena_dtcsu__solver__field__input_file_itself;
INFOARENA_DTCSU__SOLVER__BULWARK__OPEN
}
/* Step is read the given set, just skip it. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
size_t index_itself = 0;
int status_of_sorts = 0;
uint64_t value_itself = 0;
while ((INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) && (index_itself < given_set_its_size)) {
status_of_sorts = read_a_number(input_file_itself, input_buffer_itself, input_buffer_its_size, &input_buffer_its_index, &value_itself);
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != status_of_sorts) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INPUT_ERROR;
}
else {
(void) value_itself;
index_itself += 1;
}
}
}
}
/* Step is scan the number of queries itself. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
uint64_t value_from_file = 0;
int status_of_sorts = 0;
status_of_sorts = read_a_number(input_file_itself, input_buffer_itself, input_buffer_its_size, &input_buffer_its_index, &value_from_file);
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != status_of_sorts) {
exit_status_itself = status_of_sorts;
}
else {
if (UINT32_MAX < value_from_file) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INPUT_ERROR;
}
else {
if ((value_from_file < 1) || (UINT32_C(5000000) < value_from_file)) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INVALID_INPUT;
}
else {
number_of_queries_itself = (uint32_t) value_from_file;
}
}
}
}
}
/* Step is scan and solve, rinse and repeat. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
uint32_t number_of_yes_answers = 0;
size_t rank_itself = 0;
uint64_t value_itself = 0;
uint64_t image_itself = 0;
size_t index_begin = 0;
size_t index_end = 0;
size_t index_itself = 0;
bool is_in_given_set = false; /* the question */
uint64_t value_from_file = 0;
int status_of_sorts = 0;
number_of_yes_answers = 0;
rank_itself = 0;
while ((INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) && (rank_itself < number_of_queries_itself)) {
status_of_sorts = read_a_number(input_file_itself, input_buffer_itself, input_buffer_its_size, &input_buffer_its_index, &value_from_file);
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != status_of_sorts) {
exit_status_itself = status_of_sorts;
}
else {
value_itself = value_from_file;
image_itself = hash_function_itself(value_itself);
index_begin = bucket_begin_array_itself[image_itself];
index_end = bucket_begin_array_itself[image_itself + 1];
/* index_end - index_begin ∈ [0, 7], hopefully fast enough !! */
is_in_given_set = false; /* value_itself ∈ S ? (yes) or (no), S is the given set. */
index_itself = index_begin;
while ( ( !is_in_given_set) && (index_itself < index_end) ) {
if (given_set_itself[index_itself] == value_itself) {
is_in_given_set = true;
}
else {
index_itself += 1;
}
}
if (is_in_given_set) {
number_of_yes_answers += 1;
}
rank_itself += 1;
}
}
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
answer_itself = number_of_yes_answers;
}
}
}
/* Step is pass the baton. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
program_state_itself->infoarena_dtcsu__solver__field__answer_itself = answer_itself;
}
return exit_status_itself;
}
}
int infoarena_dtcsu__solver__code_up__write_answer_to_output_file (struct infoarena_dtcsu__solver__data_up__program_state * program_state_itself) {
/* Step is introduce local variables. */ {
INFOARENA_DTCSU__SOLVER__BULWARK__CLOSE
int exit_status_itself = 0;
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
INFOARENA_DTCSU__SOLVER__BULWARK__OPEN
}
/* Step is write the value, be done with it. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
FILE * output_file_itself = NULL;
uint32_t answer_itself = 0;
int status_of_sorts = 0;
output_file_itself = program_state_itself->infoarena_dtcsu__solver__field__output_file_itself;
answer_itself = program_state_itself->infoarena_dtcsu__solver__field__answer_itself;
status_of_sorts = fprintf(output_file_itself, "%" PRIu32 "\n", answer_itself);
if (status_of_sorts <= 0) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__OUTPUT_ERROR;
}
}
}
/* Step is pass the baton. */ {
return exit_status_itself;
}
}
int infoarena_dtcsu__solver__code_up__release_all_resources_down_back (struct infoarena_dtcsu__solver__data_up__program_state * program_state_itself) {
/* Step is declare and define locals, at least one, in this case. */ {
INFOARENA_DTCSU__SOLVER__BULWARK__CLOSE
int exit_status_itself = 0;
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
INFOARENA_DTCSU__SOLVER__BULWARK__OPEN
}
/* Step is free() release the input file itself. */ {
int status_of_sorts = 0;
status_of_sorts = fclose(program_state_itself->infoarena_dtcsu__solver__field__input_file_itself);
program_state_itself->infoarena_dtcsu__solver__field__input_file_itself = NULL;
if (0 != status_of_sorts) {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != status_of_sorts) {
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__NAY_FAILURE__INPUT_ERROR;
}
}
}
/* Step is free() release the input buffer itself. */ {
free(program_state_itself->infoarena_dtcsu__solver__field__input_buffer_itself);
program_state_itself->infoarena_dtcsu__solver__field__input_buffer_itself = NULL;
program_state_itself->infoarena_dtcsu__solver__field__input_buffer_its_size = 0;
}
/* Step is free() release the given set itself. */ {
free(program_state_itself->infoarena_dtcsu__solver__field__given_set_itself);
program_state_itself->infoarena_dtcsu__solver__field__given_set_itself = NULL;
program_state_itself->infoarena_dtcsu__solver__field__given_set_its_size = 0;
}
/* Step is free() release the bucket begin array itself. */ {
free(program_state_itself->infoarena_dtcsu__solver__field__bucket_begin_array_itself);
program_state_itself->infoarena_dtcsu__solver__field__bucket_begin_array_itself = NULL;
program_state_itself->infoarena_dtcsu__solver__field__bucket_begin_array_its_size = 0;
}
/* Step is free() release the bucket count array itself. */ {
free(program_state_itself->infoarena_dtcsu__solver__field__bucket_count_array_itself);
program_state_itself->infoarena_dtcsu__solver__field__bucket_count_array_itself = NULL;
program_state_itself->infoarena_dtcsu__solver__field__bucket_count_array_its_size = 0;
}
/* Step is free() release the bucket size array itself. */ {
free(program_state_itself->infoarena_dtcsu__solver__field__bucket_size_array_itself);
program_state_itself->infoarena_dtcsu__solver__field__bucket_size_array_itself = NULL;
program_state_itself->infoarena_dtcsu__solver__field__bucket_size_array_its_size = 0;
}
/* Step is free() release the program state itself. */ {
free(program_state_itself);
program_state_itself = NULL;
}
/* Step is pass the baton, next one to carry on; good bye! */ {
return exit_status_itself;
}
}
int main (void) {
/* Step is declare and define the locals. */ {
INFOARENA_DTCSU__SOLVER__BULWARK__CLOSE
int exit_status_itself = 0;
struct infoarena_dtcsu__solver__data_up__program_state * program_state_itself = NULL;
exit_status_itself = INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
INFOARENA_DTCSU__SOLVER__BULWARK__OPEN
}
/* Step is acquire all the resources, up front. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
int status_of_sorts = 0;
struct infoarena_dtcsu__solver__data_up__program_state * pointer_itself = NULL;
status_of_sorts = infoarena_dtcsu__solver__code_up__acquire_all_resources_up_front(&pointer_itself);
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != status_of_sorts) {
exit_status_itself = status_of_sorts;
}
else {
program_state_itself = pointer_itself;
}
}
}
/* Step is build the hash table, already. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
int status_of_sorts = 0;
status_of_sorts = infoarena_dtcsu__solver__code_up__build_the_hash_table_already(program_state_itself);
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != status_of_sorts) {
exit_status_itself = status_of_sorts;
}
}
}
/* Step is skip given set and solve queries from the input file. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
int status_of_sorts = 0;
status_of_sorts = infoarena_dtcsu__solver__code_up__read_input_solve_all_queries(program_state_itself);
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != status_of_sorts) {
exit_status_itself = status_of_sorts;
}
}
}
/* Step is write the answer into the output file. */ {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
int status_of_sorts = 0;
status_of_sorts = infoarena_dtcsu__solver__code_up__write_answer_to_output_file(program_state_itself);
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != status_of_sorts) {
exit_status_itself = status_of_sorts;
}
}
}
/* Step is release the resources, down!, back! */ {
if (NULL != program_state_itself) {
int status_of_sorts = 0;
status_of_sorts = infoarena_dtcsu__solver__code_up__release_all_resources_down_back(program_state_itself);
program_state_itself = NULL;
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != status_of_sorts) {
if (INFOARENA_DTCSU__SOLVER__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status_itself) {
exit_status_itself = status_of_sorts;
}
}
}
}
/* Step is pass the baton, done, or at least stop! */ {
return exit_status_itself;
}
}
Marius B mgnt