結果

問題 No.9 モンスターのレベル上げ
ユーザー magicalkozo
提出日時 2023-08-14 15:38:31
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,586 bytes
コンパイル時間 1,123 ms
コンパイル使用メモリ 35,612 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-22 14:02:26
合計ジャッジ時間 2,783 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 18 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

typedef struct PairingHeap PHeap;
struct PairingHeap {
    PHeap* subheaps;
    PHeap* next;
};

typedef bool (*pheap_comparator_func)(PHeap*, PHeap*);

PHeap* meld_pheap(PHeap *left, PHeap *right, pheap_comparator_func comp) {
    if (!left)
        return right;
    if (!right)
        return left;
    if (comp(left, right)) {
        if (left->subheaps)
            right->next = left->subheaps;
        left->subheaps = right;
        return left;
    } else {
        if (right->subheaps)
            left->next = right->subheaps;
        right->subheaps = left;
        return right;
    }
}
PHeap* push_pheap(PHeap *heap, PHeap *elem, pheap_comparator_func comp) {
	elem->subheaps = NULL;
	elem->next = NULL;
	return meld_pheap(elem, heap, comp);
}
PHeap* merge_pairs_pheap(PHeap *list, pheap_comparator_func comp) {
	if (!list) {
		return NULL;
	} else if (list->next == NULL) {
		return list;
	} else {
		PHeap *next = list->next;
		list->next = NULL;
		PHeap *rest = next->next;
		next->next = NULL;
		return meld_pheap(meld_pheap(list, next, comp), merge_pairs_pheap(rest, comp), comp);
	}
}
PHeap* pop_pheap(PHeap *heap, pheap_comparator_func comp) {
	PHeap *subs = heap->subheaps;
	return merge_pairs_pheap(subs, comp);
}
void visit_heap_pheap(PHeap *heap, void (*func)(PHeap *)) {
	if (!heap)
        return;
	func(heap);
	visit_heap_pheap(heap->subheaps, func);
	visit_heap_pheap(heap->next, func);
}
void* or_pheap(void *a, uintptr_t b) {
	return (a == NULL) ? (void *)b : a;
}

#define container_of(ptr, type, member) ((type *)((uint8_t *)(ptr) - offsetof(type, member)))
#define PHEAP_push(HEAP, ELEM, COMP) container_of(push_pheap((HEAP) ? &(HEAP)->pheap : NULL, &(ELEM)->pheap, (COMP)), struct Pair, pheap)
#define PHEAP_visit(HEAP, F) (visit_heap_pheap(&(HEAP)->pheap, (F)))
#define PHEAP_value(type, HEAP) (container_of(HEAP, type, pheap))
#define PHEAP_pop(HEAP, COMP) container_of(or_pheap(pop_pheap(&(HEAP)->pheap, (COMP)), offsetof(struct Pair, pheap)), struct Pair, pheap)

struct Pair {
    int fst;
    int snd;
    PHeap pheap;
};

bool comparator(PHeap *left, PHeap *right) {
    struct Pair* l = PHEAP_value(struct Pair, left);
    struct Pair* r = PHEAP_value(struct Pair, right);
    return l->fst == r->fst ? l->snd < r->snd : l->fst < r->fst;
}

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;
    struct Pair *elem = (struct Pair*)malloc(sizeof(struct Pair));
    for (int i = 0; i < N; i++) {
        struct Pair *heap = NULL;
        int heap_size = 0;
        for (int j = 0; j < N; j++) {
            elem->fst = A[j];
            elem->snd = 0;
            heap = PHEAP_push(heap, elem, comparator);
            heap_size++;
        }
        for (int j = 0; j < N; j++) {
            struct Pair *min = heap;
            heap = PHEAP_pop(heap, comparator);
            elem->fst = min->fst + B[i + j] / 2;
            elem->snd = min->snd + 1;
            PHEAP_push(heap, elem, comparator);
        }
        int tmp = 0;
        while (heap_size) {
            struct Pair *min = heap;
            heap = PHEAP_pop(heap, comparator);
            tmp = tmp > min->snd ? tmp : min->snd;
            heap_size--;
        }
        m = m < tmp ? m : tmp;
    }
    printf("%d\n", m);
    return 0;
}
0