結果
| 問題 | No.9 モンスターのレベル上げ |
| ユーザー |
 magicalkozo
|
| 提出日時 | 2023-08-14 13:21:30 |
| 言語 | C (gcc 12.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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | WA | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
コンパイルメッセージ
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);
| ^~~~~~~~~
ソースコード
#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;
}