結果

問題 No.9 モンスターのレベル上げ
ユーザー magicalkozomagicalkozo
提出日時 2023-08-14 13:23:28
言語 C
(gcc 12.3.0)
結果
RE  
実行時間 -
コード長 4,789 bytes
コンパイル時間 232 ms
コンパイル使用メモリ 32,512 KB
実行使用メモリ 13,888 KB
最終ジャッジ日時 2024-05-02 01:36:24
合計ジャッジ時間 6,988 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'main':
main.c:171:38: warning: initialization of 'struct pair_wrapper *' from incompatible pointer type 'node *' {aka 'struct heap_elem *'} [-Wincompatible-pointer-types]
  171 |             struct pair_wrapper* p = pop_pheap(&pq, NULL);
      |                                      ^~~~~~~~~
main.c:178:38: warning: initialization of 'struct pair_wrapper *' from incompatible pointer type 'node *' {aka 'struct heap_elem *'} [-Wincompatible-pointer-types]
  178 |             struct pair_wrapper* p = pop_pheap(&pq, NULL);
      |                                      ^~~~~~~~~

ソースコード

diff # 

#include <assert.h>
#include <stdio.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>

typedef struct heap_elem node;
struct heap_elem {
    node *prev;
    node *next;
    node *child;
};

typedef bool heap_less_func(const node *a, const node *b, void *aux);

typedef struct pheap_t {
    size_t size;
    node *root;
    heap_less_func *less;
} PairingHeap;

void init_pheap(PairingHeap *h, heap_less_func *less) {
    h->size = 0;
    h->root = NULL;
    h->less = less;
}
node* merge_node(node *a, node *b, heap_less_func *less, void *aux) {
    if (less(a, b, aux)) {
        if (a->child != NULL)
            a->child->prev = b;
        if (b->next != NULL)
            b->next->prev = a;
        a->next = b->next;
        b->next = a->child;
        a->child = b;
        b->prev = a;
        return a;
    }
    if (b->child != NULL)
        b->child->prev = a;
    if (a->prev != NULL && a->prev->child != a)
        a->prev->next = b;
    b->prev = a->prev;
    a->prev = b;
    a->next = b->child;
    b->child = a;
    return b;
}
void push_pheap(PairingHeap *h, node *elem, void *aux) {
    h->size++;

    elem->prev = NULL;
    elem->next = NULL;
    elem->child = NULL;

    if (h->root == NULL)
        h->root = elem;
    else
        h->root = merge_node(elem, h->root, h->less, aux);
}
node* merge_right_node(node *a, heap_less_func *less, void *aux) {
    node *b;
    for (b = NULL; a != NULL; a = b->next) {
        if ((b = a->next) == NULL)
            return a;
        b = merge_node(a, b, less, aux);
    }
    return b;
}
node* merge_left_node(node *a, heap_less_func *less, void *aux) {
    node *b;
    for (b = a->prev; b != NULL; b = a->prev)
        a = merge_node(b, a, less, aux);
    return a;
}
node* merge_subheaps_node(node *a, heap_less_func *less, void *aux) {
    a->child->prev = NULL;
    node *e;
    e = merge_right_node(a->child, less, aux);
    e = merge_left_node(e, less, aux);
    return e;
}
void detach_subheap_node(node *elem) {
    if (elem->prev->child == elem)
        elem->prev->child = elem->next;
    else
        elem->prev->next = elem->next;
    if (elem->next != NULL)
        elem->next->prev = elem->prev;
    elem->prev = NULL;
    elem->next = NULL;
}
node* pop_pheap(PairingHeap *h, void *aux) {
    assert (h->size > 0);
    h->size--;
    node *root = h->root;
    if (root->child == NULL) {
        h->root = NULL;
        return root;
    }
    h->root = merge_subheaps_node(root, h->less, aux);
    return root;
}
void remove_pheap(PairingHeap *h, node *elem, void *aux) {
    if (elem == h->root) {
      pop_pheap(h, aux);
      return;
    }
    assert (h->size > 0);
    h->size--;
    detach_subheap_node(elem);
    elem = merge_subheaps_node(elem, h->less, aux);
    h->root = merge_node(h->root, elem, h->less, aux);
}
node* top_pheap(PairingHeap *h) {
    return h->root; 
}
bool is_empty_pheap(PairingHeap *h) {
    return h->root == NULL;
}
size_t size_pheap(PairingHeap *h) {
    return h->size;
}
void increase_pheap(PairingHeap *h, node *elem, void *aux) {
    remove_pheap(h, elem, aux);
    push_pheap(h, elem, aux);
}
void decrease_pheap(PairingHeap *h, node *elem, void *aux) {
    if (elem->prev == NULL)
        return;
    detach_subheap_node(elem);
    h->root = merge_node(h->root, elem, h->less, aux); 
}

#define heap_entry(HEAP_ELEM, STRUCT, MEMBER) ((STRUCT *) ((uint8_t *) &(HEAP_ELEM)->child - offsetof(STRUCT, MEMBER.child)))
#define HEAP_INITIALIZER(NAME, LESS) { 0, NULL, (LESS) }

struct pair_wrapper {
    int a, b;
    node elem;
};

bool pair_less(const node * a, const node *b, void *aux) {
    struct pair_wrapper *x, *y;
    x = heap_entry(a, struct pair_wrapper, elem);
    y = heap_entry(b, struct pair_wrapper, elem);
    return x->a == y->a ? x->b < y->b : x->a < y->a;
}

int main(void) {
    int N;
    scanf("%d", &N);
    int A[3030], B[3030];
    for (int i = 0; i < N; i++)
        scanf("%d", A + i);
    for (int i = 0; i < N; i++) {
        scanf("%d", B + i);
        B[i + N] = B[i];
    }
    int m = INT32_MAX;
    for (int i = 0; i < N; i++) {
        PairingHeap pq;
        init_pheap(&pq, pair_less);
        for (int j = 0; j < N; j++) {
            struct pair_wrapper p;
            p.a = A[j], p.b = 0;
            push_pheap(&pq, &p.elem, NULL);
        }
        for (int j = 0; j < N; j++) {
            struct pair_wrapper* p = pop_pheap(&pq, NULL);
            p->a += B[i + j] / 2;
            p->b += 1;
            push_pheap(&pq, &(p->elem), NULL);
        }
        int tmp = 0;
        while (!is_empty_pheap(&pq)) {
            struct pair_wrapper* p = pop_pheap(&pq, NULL);
            tmp = tmp > p->b ? tmp : p->b;
        }
        m = m < tmp ? m : tmp;
    }
    printf("%d\n", m);
    return 0;
}
0