結果

問題 No.9 モンスターのレベル上げ
ユーザー magicalkozo
提出日時 2023-08-14 13:21:30
言語 C
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 4,780 bytes
コンパイル時間 420 ms
コンパイル使用メモリ 32,128 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-22 10:56:07
合計ジャッジ時間 3,521 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 1 RE * 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:174:29: warning: passing argument 2 of 'push_pheap' from incompatible pointer type [-Wincompatible-pointer-types]
  174 |             push_pheap(&pq, p, NULL);
      |                             ^
      |                             |
      |                             struct pair_wrapper *
main.c:50:39: note: expected 'node *' {aka 'struct heap_elem *'} but argument is of type 'struct pair_wrapper *'
   50 | void push_pheap(PairingHeap *h, node *elem, void *aux) {
      |                                 ~~~~~~^~~~
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, 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