Участник:Easik/HELPR2D2

Материал из DISCOPAL
Перейти к: навигация, поиск

C / gcc

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
/* Last layer must fit 100,000 ships => 2 ^ 17 + all other layers, hence 2 ^ 18 */
#define segrement_tree_nodes 1 << 18
 
/* Global declaration of a segment tree */
 
typedef struct {
    int min_capacity;
    int max_capacity;
} Node;
 
Node segment_tree[segrement_tree_nodes];
 
void init_segment_tree(int idx, int ship_min_idx, int ship_max_idx, int capacity);
int update_segment_tree(int idx, int ship_min_idx, int ship_max_idx, int weight);
 
int main() {
 
    int i, j, m;
    int T, K, r, v;
    int n, loaded_ship_idx;
    int total_loaded_weight, max_used_ship_idx;
    int used_ships, underload;
    char buffer[1000];
 
    scanf("%d", &T);
    for (i = 0; i < T; i++) {
 
        scanf("%d", &K);
        scanf("%d", &n);
 
        /* Init or reset segment tree with initial ships' capacities */
        init_segment_tree(1, 0, 100000-1, K);
        j = 0;
        total_loaded_weight = 0;
        max_used_ship_idx = 0;
 
        /* Load each container */
        while (j < n) {
 
            scanf("%s", buffer);
            if (buffer[0] == 'b') {
 
                scanf("%d %d", &r, &v);
                j += r;
 
                for (m = 0; m < r; m++) {
 
                    /* Load ship, update min/max capacities, calc loaded ships */
                    loaded_ship_idx = update_segment_tree(1, 0, 100000-1, v);
                    max_used_ship_idx = (max_used_ship_idx >= loaded_ship_idx) ? max_used_ship_idx : loaded_ship_idx;
                    total_loaded_weight += v;
 
                }
 
            } else {
 
                v = atoi(buffer);
                j++;
 
                /* Load ship, update min/max capacities, calc loaded ships */
                loaded_ship_idx = update_segment_tree(1, 0, 100000-1, v);
                max_used_ship_idx = (max_used_ship_idx >= loaded_ship_idx) ? max_used_ship_idx : loaded_ship_idx;
                total_loaded_weight += v;
 
            }
 
        }
 
        /* Output results */
        used_ships = max_used_ship_idx + 1;
        underload = used_ships * K - total_loaded_weight;
        printf("%d %d\n", used_ships, underload);
 
    }
 
    return 0;
}
 
void init_segment_tree(int idx, int ship_min_idx, int ship_max_idx, int capacity) {
 
    /* Node-leaf with a single ship idx */
    if (ship_min_idx == ship_max_idx) {
 
        segment_tree[idx].min_capacity = capacity;
        segment_tree[idx].max_capacity = capacity;
        return;
 
    }
 
    /* Subtree params */
    int left_idx = 2 * idx;
    int right_idx = left_idx + 1;
    int ship_mid_idx = floor((ship_min_idx + ship_max_idx) / 2.0);
 
    /* Init left & right subtrees */
    init_segment_tree(left_idx, ship_min_idx, ship_mid_idx, capacity);
    init_segment_tree(right_idx, ship_mid_idx + 1, ship_max_idx, capacity);
 
    /* Init min/max capacities for node's subtrees */
    segment_tree[idx].min_capacity = capacity;
    segment_tree[idx].max_capacity = capacity;
 
}
 
int update_segment_tree(int idx, int ship_min_idx, int ship_max_idx, int weight) {
 
    /* No capacity to place a weight in subtrees */
    if (weight > segment_tree[idx].max_capacity) {
 
        return -1;
 
    }
 
    /* Place a weight into a node with a single ship idx */
    if (ship_min_idx == ship_max_idx) {
 
        segment_tree[idx].min_capacity -= weight;
        segment_tree[idx].max_capacity -= weight;
        return ship_min_idx;
 
    }
 
    /* Subtree params */
    int left_idx = 2 * idx;
    int right_idx = left_idx + 1;
    int ship_mid_idx = floor((ship_min_idx + ship_max_idx) / 2.0);
 
    /* Try placing weight into left subtree (with smaller ship indices) */
    int upd_status = update_segment_tree(left_idx, ship_min_idx, ship_mid_idx, weight);
 
    /* Left subtree is occupied - try right subtree */
    if (upd_status == -1) {
 
        upd_status = update_segment_tree(right_idx, ship_mid_idx + 1, ship_max_idx, weight);
 
    }
 
    /* Update min/max capacities for subtrees */
    segment_tree[idx].min_capacity = (segment_tree[left_idx].min_capacity <= segment_tree[right_idx].min_capacity) ? segment_tree[left_idx].min_capacity : segment_tree[right_idx].min_capacity;
    segment_tree[idx].max_capacity = (segment_tree[left_idx].max_capacity >= segment_tree[right_idx].max_capacity) ? segment_tree[left_idx].max_capacity : segment_tree[right_idx].max_capacity;
 
    return upd_status;
 
}