Cod sursa(job #2943624)
| Utilizator |  Marius B mgnt |
Data | 21 noiembrie 2022 13:07:02 |
|---|---|---|---|
| Problema | Schi | Scor | 10 |
| Compilator | c-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 100.34 kb |
#define SCHI__FOLD__SCOPE
#ifdef SCHI__FOLD__SCOPE /* folding the diez include plus section */
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <stddef.h>
#include <stdbool.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#define SCHI__CURLY_BRACKETS_BEGIN {
#define SCHI__CURLY_BRACKETS_END }
#define SCHI__INVERTED_CURLY_BRACKETS_BEGIN SCHI__CURLY_BRACKETS_END
#define SCHI__INVERTED_CURLY_BRACKETS_END SCHI__CURLY_BRACKETS_BEGIN
#endif
#ifdef SCHI__FOLD__SCOPE /* folding the exit codes values section */
static int const SCHI__EXIT_CODE__SUCCESS__ALL_HUNKY_DORY = 0;
static int const SCHI__EXIT_CODE__FAILURE__FOPEN__INPUT_FILE = 1;
static int const SCHI__EXIT_CODE__FAILURE__FCLOSE__INPUT_FILE = 2;
static int const SCHI__EXIT_CODE__FAILURE__FSCANF__COULD_NOT_DO_ITS_ONE_JOB = 3;
static int const SCHI__EXIT_CODE__FAILURE__INVALID_INPUT = 4;
static int const SCHI__EXIT_CODE__FAILURE__FOPEN__OUTPUT_FILE = 5;
static int const SCHI__EXIT_CODE__FAILURE__FCLOSE__OUTPUT_FILE = 6;
static int const SCHI__EXIT_CODE__FAILURE__FPRINTF_COULD_NOT_DO_ITS_ONE_JOB = 7;
#endif
#ifdef SCHI__FOLD__SCOPE /* folding the constants section */
#define SCHI__CONST__MAX_NUM_CONCURENTS 30000 // MAX_NUM_CONCURENTS := 30000, from the problem statement.
#define SCHI__CONST__MAX_NUM_BLOCKS 174 // MAX_NUM_BLOCKS := ⌈√(MAX_NUM_CONCURENTS)⌉.
#define SCHI__CONST__MAX_NUM_BYTES 3750 // MAX_NUM_BYTES := ⌈MAX_NUM_CONCURENTS / 8⌉ (in bitsets).
#endif
#ifdef SCHI__FOLD__SCOPE /* folding the data section */
static size_t schi__data__number_of_competitors = 0; // “n”
static size_t schi__data__rank_instant [SCHI__CONST__MAX_NUM_CONCURENTS]; // “rank[1 … n]”, at current t
static size_t schi__data__rank_final [SCHI__CONST__MAX_NUM_CONCURENTS]; // “rank[1 … n]”, at final t
static bool schi__data__rank_solved [SCHI__CONST__MAX_NUM_CONCURENTS]; // “rank[1 … n]”, solved or no
static uint8_t schi__data__block_bitset[SCHI__CONST__MAX_NUM_BLOCKS][SCHI__CONST__MAX_NUM_BYTES]; // “bitset[j]“
static size_t schi__data__block_origin[SCHI__CONST__MAX_NUM_BLOCKS]; // “origin[j]”
static size_t schi__data__block_size = 0; // “B”, the block size
static size_t schi__data__number_of_blocks = 0; // “⌈n/B⌉”, the number of blocks
static size_t schi__data__bitset_byte_size = 0; // bit-set sizez, in bytes
// B := ⌈√(n)⌉, where n is the number of competitors;
// B is the block size in our square root decomposition.
// block[j] := {x; x ∈ ℤ, j·B ≤ x < min(n, (j + 1)·B)}, a ghost variable,
// a variable of no consequence to the program, but useful in documenting it, or
// in reasoning about its correctness, etc. why3 talks about such things.
// image[j] := {rank[x]; x ∈ block[j]}, a ghost variable.
// y ∈ image[j] ⇔ (y − origin[j]) ∈ bitset[j],
// an relation described easily, with help from our ghost variables above!
// {1} = 1 + [1]; [k] = {x; x ∈ ℤ, 0 ≤ x < k}; [1] = {0}, horsing around with notation.
#endif
#ifdef SCHI__FOLD__SCOPE /* folding the block related routines section */
static size_t schi__code__min (size_t a, size_t b) {
return ((a < b) ? a : b);
}
static size_t schi__code__block_begin (size_t block_index) {
return (block_index * schi__data__block_size);
}
static size_t schi__code__block_end (size_t block_index) {
return schi__code__min((block_index + 1) * schi__data__block_size, schi__data__number_of_competitors);
}
static size_t schi__code__compute_the_index_of_block_containing_the_given (size_t index) {
/* For index ∈ ℤ, 0 ≤ index < schi__data__number_of_competitors, it gives the index of the block containing this index. */
return (index / schi__data__block_size);
}
#endif
#ifdef SCHI__FOLD__SCOPE /* folding the initializations section */
static void schi__code__initialize_the_bitsets_and_everything_else (void) {
/* Determine the block size.
* ========================= */ {
size_t const n = schi__data__number_of_competitors;
double const n2 = n;
size_t const bs = ((size_t) ceil(sqrt(n2)));
schi__data__block_size = bs;
}
/* Determine the number of blocks.
* =============================== */ {
size_t const n = schi__data__number_of_competitors;
size_t const bs = schi__data__block_size;
double const n2 = n;
size_t const bc = ((size_t)ceil(n2 / bs));
schi__data__number_of_blocks = bc;
}
/* Determine the number of bytes to be used for each bitset.
* ========================================================= */ {
size_t const n = schi__data__number_of_competitors;
size_t const yc = ((n / 8) + ((0 != (n % 8)) ? 1 : 0));
schi__data__bitset_byte_size = yc;
}
/* Block by block, store in its corresponding bitset, the ranks of its constituent competitors.
* ============================================================================================ */ {
size_t const bitset_byte_size = schi__data__bitset_byte_size;
size_t const number_of_blocks = schi__data__number_of_blocks;
size_t block_index = 0;
while (number_of_blocks > block_index) {
/* Memset the current block, to zero.
* ================================== */ {
memset(schi__data__block_bitset[block_index], 0, bitset_byte_size);
}
/* Store the values from the rank array, in the bitset.
* ==================================================== */ {
size_t const block_begin = schi__code__block_begin(block_index);
size_t const block_end = schi__code__block_end(block_index);
uint8_t * bitset = schi__data__block_bitset[block_index];
size_t competitor = 0;
size_t bit_index = 0;
size_t bit_in_memory = 0;
size_t bit_in_byte = 0;
uint8_t const one_uint8_t = 1;
uint8_t bit_mask = 0;
uint8_t bitset_byte = 0;
competitor = block_begin;
while (block_end > competitor) {
/* Query, update.
* ============== */
bit_index = schi__data__rank_instant[competitor];
bit_in_memory = bit_index / 8;
bit_in_byte = bit_index % 8;
bit_mask = one_uint8_t << bit_in_byte;
bitset_byte = bitset[bit_in_memory];
bitset_byte = bitset_byte | bit_mask;
bitset[bit_in_memory] = bitset_byte;
/* Carry on.
* ========= */
competitor += 1;
}
schi__data__block_origin[block_index] = 0;
}
/* Carry on.
* ========= */
block_index += 1;
}
}
/* Nothing is solved, in the beginning, no surprise here.
* ====================================================== */ {
size_t competitor = 0;
while (schi__data__number_of_competitors > competitor) {
schi__data__rank_solved[competitor] = false;
competitor += 1;
}
}
/* Initialize the competitor final rank array.
* =========================================== */ {
/* NOTE: This is a inconsequential initialization, but
* it is debug friendly to have a known sensible value.
*/
size_t competitor = 0;
while (schi__data__number_of_competitors > competitor) {
schi__data__rank_final[competitor] = schi__data__number_of_competitors;
competitor += 1;
}
}
}
#endif
#ifdef SCHI__FOLD__SCOPE /* folding the sqrt decomposition query routine */
static size_t schi__code__scan_competitor (size_t block_index, size_t rank) {
/* Quickly scan in this block sure to contain rank, the last competitor where rank occurs.
* ======================================================================================= */ {
size_t competitor2 = schi__data__number_of_competitors;
size_t const block_origin = schi__data__block_origin[block_index];
size_t const block_begin = schi__code__block_begin(block_index);
size_t const block_end = schi__code__block_end(block_index);
size_t competitor = block_end;
while (block_begin < competitor) {
competitor -= 1;
if ((block_origin + schi__data__rank_instant[competitor]) == rank) {
competitor2 = competitor;
break;
}
}
return competitor2;
}
}
static size_t schi__code__query_competitor (size_t rank) {
/* Quickly find out the last block to contain rank, and, in this block, the last position or index of given rank.
* ============================================================================================================== */ {
size_t competitor = schi__data__number_of_competitors;
size_t block_index = 0;
size_t block_origin = 0;
uint8_t const * block_bitset = NULL;
size_t bit_index = 0;
size_t bit_in_memory = 0;
size_t bit_in_byte = 0;
uint8_t const one_uint8_t = 1;
uint8_t bit_mask = 0;
uint8_t bitset_byte = 0;
block_index = schi__data__number_of_blocks;
while (0 < block_index) {
block_index -= 1;
block_origin = schi__data__block_origin[block_index];
if (block_origin <= rank) {
block_bitset = schi__data__block_bitset[block_index];
bit_index = rank - block_origin;
bit_in_memory = bit_index / 8;
bit_in_byte = bit_index % 8;
bit_mask = one_uint8_t << bit_in_byte;
bitset_byte = block_bitset[bit_in_memory];
if (0 != (bitset_byte & bit_mask)) {
competitor = schi__code__scan_competitor (block_index, rank);
break;
}
}
}
return competitor;
}
}
#endif
#ifdef SCHI__FOLD__SCOPE /* folding the sqrt decomposition update routine */
static void schi__code__update_remaining_competitors (size_t recently_solved_competitor) {
/* Initialize a small bunch of variables useful throughout most parts of the current routine.
* ========================================================================================== */ {
SCHI__INVERTED_CURLY_BRACKETS_BEGIN
size_t const block_index = schi__code__compute_the_index_of_block_containing_the_given(recently_solved_competitor);
SCHI__INVERTED_CURLY_BRACKETS_END
}
/* Update the ranks in the block containing the index, all ranks but that of our index which remains unchanged.
* ============================================================================================================ */ {
size_t const block_origin = schi__data__block_origin[block_index];
size_t * rank_instant = schi__data__rank_instant;
size_t const block_begin = schi__code__block_begin(block_index);
size_t const block_end = schi__code__block_end(block_index);
size_t solved_rank = rank_instant[recently_solved_competitor] + block_origin;
size_t competitor = block_begin;
/* Save the instant rank for the recently solved competitor, as its final rank, and mark this competitor as solved.
* ================================================================================================================ */ {
schi__data__rank_final[recently_solved_competitor] = solved_rank;
schi__data__rank_solved[recently_solved_competitor] = true;
}
/* Adjust the instant ranks of the competitors before, with higher final rankings.
* =============================================================================== */ {
/* NOTE: (1) the competitors before the recently solved competitor, in the start order.
* (2) the competitors with final rankings greater than the final ranking of the recently solved competitor. */
competitor = block_begin;
while (recently_solved_competitor > competitor) {
if ( !schi__data__rank_solved[competitor] ) {
rank_instant[competitor] += 1;
}
competitor += 1;
}
}
/* Rebuild the bit set associated with the block containing the recently solved competitor.
* ======================================================================================== */ {
uint8_t * bitset = schi__data__block_bitset[block_index];
size_t bit_index = 0;
size_t bit_in_memory = 0;
size_t bit_in_byte = 0;
uint8_t const one_uint8_t = 1;
uint8_t bit_mask = 0;
uint8_t bitset_byte = 0;
/* Clear first.
* ============ */
memset(schi__data__block_bitset[block_index], 0, schi__data__bitset_byte_size);
/* Mark next.
* ========== */
competitor = block_begin;
while (block_end > competitor) {
/* Set bit.
* ========== */ {
if ( !schi__data__rank_solved[competitor]) {
bit_index = rank_instant[competitor];
bit_in_memory = bit_index / 8;
bit_in_byte = bit_index % 8;
bit_mask = one_uint8_t << bit_in_byte;
bitset_byte = bitset[bit_in_memory];
bitset_byte = bitset_byte | bit_mask;
bitset[bit_in_memory] = bitset_byte;
}
}
/* Carry on.
* ========= */
competitor += 1;
}
}
}
/* Update all the blocks preceding the block containing the index, by tweaking their origin values.
* ================================================================================================ */ {
size_t * block_origin = schi__data__block_origin;
size_t block_index0 = 0;
while (block_index0 < block_index) {
block_origin[block_index0] += 1;
block_index0 += 1;
}
}
}
#endif
#ifdef SCHI__FOLD__SCOPE /* folding the whole read problem, solve proble, write answer story */
static void schi__code__solve_the_given_problem_instance (void) {
/* Initialize everything, already.
* =============================== */ {
schi__code__initialize_the_bitsets_and_everything_else();
}
/* Step by step, determine the competitiors in the increasing order of their final ranks.
* ====================================================================================== */ {
size_t rank = 0;
size_t competitor = 0;
rank = 0;
while (schi__data__number_of_competitors > rank) {
competitor = schi__code__query_competitor(rank);
schi__code__update_remaining_competitors(competitor);
rank += 1;
}
}
}
static int schi__code__read_the_instance (void) {
int exit_code = SCHI__EXIT_CODE__SUCCESS__ALL_HUNKY_DORY;
int status_code = 0;
FILE * f = NULL;
size_t n = 0;
size_t j = 0;
size_t r = 0;
while (true) {
f = fopen("schi.in", "r");
if (NULL == f) {
exit_code = SCHI__EXIT_CODE__FAILURE__FOPEN__INPUT_FILE;
break;
}
status_code = fscanf(f, "%zu", &n);
if (1 != status_code) {
exit_code = SCHI__EXIT_CODE__FAILURE__FSCANF__COULD_NOT_DO_ITS_ONE_JOB;
break;
}
if ((1 > n) || (/* SCHI__CONST__MAX_N */ 30000 < n)) {
exit_code = SCHI__EXIT_CODE__FAILURE__INVALID_INPUT;
break;
}
j = 0;
while (n > j) {
j += 1;
status_code = fscanf(f, "%zu", &r);
if (1 != status_code) {
exit_code = SCHI__EXIT_CODE__FAILURE__FSCANF__COULD_NOT_DO_ITS_ONE_JOB;
break;
}
if ((1 > r) || (j < r)) {
exit_code = SCHI__EXIT_CODE__FAILURE__INVALID_INPUT;
break;
}
schi__data__rank_instant[j - 1] = r - 1; /* 0 based ranking, inwardly */
}
if (SCHI__EXIT_CODE__SUCCESS__ALL_HUNKY_DORY != exit_code) {
break;
}
break;
}
if (NULL != f) {
status_code = fclose(f);
if (0 != status_code) {
if (SCHI__EXIT_CODE__SUCCESS__ALL_HUNKY_DORY == exit_code) {
exit_code = SCHI__EXIT_CODE__FAILURE__FCLOSE__INPUT_FILE;
}
}
}
if (SCHI__EXIT_CODE__SUCCESS__ALL_HUNKY_DORY == exit_code) {
schi__data__number_of_competitors = n;
}
return exit_code;
}
static int schi__code__write_the_answer (void) {
size_t const * rank_final = schi__data__rank_final;
size_t const count = schi__data__number_of_competitors;
int exit_code = SCHI__EXIT_CODE__SUCCESS__ALL_HUNKY_DORY;
int status = 0;
FILE * g = NULL;
size_t place = 0;
while (true) {
g = fopen("schi.out", "w");
if (NULL == g) {
exit_code = SCHI__EXIT_CODE__FAILURE__FOPEN__OUTPUT_FILE;
break;
}
place = 0;
while (count > place) {
status = fprintf(g, "%zu\n", (1 + rank_final[place])); /* 1 based ranking, outwardly */
if (0 >= status) {
exit_code = SCHI__EXIT_CODE__FAILURE__FPRINTF_COULD_NOT_DO_ITS_ONE_JOB;
break;
}
place += 1;
}
if (SCHI__EXIT_CODE__SUCCESS__ALL_HUNKY_DORY != exit_code) {
break;
}
break;
}
if (NULL != g) {
status = fclose(g);
if (0 != status) {
if (SCHI__EXIT_CODE__SUCCESS__ALL_HUNKY_DORY != status) {
status = SCHI__EXIT_CODE__FAILURE__FCLOSE__OUTPUT_FILE;
}
}
}
return exit_code;
}
static int schi__code__demo (void) {
int exit_code = schi__code__read_the_instance();
if (SCHI__EXIT_CODE__SUCCESS__ALL_HUNKY_DORY == exit_code) {
schi__code__solve_the_given_problem_instance();
exit_code = schi__code__write_the_answer();
}
return exit_code;
}
int main (void) {
return schi__code__demo();
}
#endif
