#903910 (C) No.9 モンスターのレベル上げ

• 問題: No.9 モンスターのレベル上げ
• ユーザー: magicalkozo
• 提出日時: 2023-08-14 17:11:19
• 言語: C (gcc 13.3.0)
• 結果: AC
• 実行時間: 2,673 ms / 5,000 ms
• コード長: 7,567 bytes
• コンパイル時間: 381 ms
• コンパイル使用メモリ: 37,276 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-22 16:13:57
• 合計ジャッジ時間: 24,879 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
other	AC * 20

ソースコード

#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Pair {
    int fst;
    int snd;
} Key;

typedef struct {
    Key key;
    void* value;
} data;

bool comp_greater(Key a, Key b) {
    return a.fst == b.fst ? a.snd > b.snd : a.fst > b.fst;
}
bool comp_gt(Key a, Key b) {
    return a.fst == b.fst ? a.snd >= b.snd : a.fst >= b.fst;
}
bool comp_less(Key a, Key b) {
    return a.fst == b.fst ? a.snd < b.snd : a.fst < b.fst;
}
bool comp_lt(Key a, Key b) {
    return a.fst == b.fst ? a.snd <= b.snd : a.fst <= b.fst;
}
bool comp_equal(Key a, Key b) {
    return a.fst == b.fst && a.snd == b.snd;
}

typedef struct FibonacciNode FNode;
struct FibonacciNode {
    FNode* left;
    FNode* right;
    FNode* parent;
    FNode* child;
    Key key;
    void* value;
    bool mark;
    int degree;
};

typedef FNode FHeap;
typedef FNode FElem;

FNode* init_fnode(Key key, void* value) {
    FNode* new_node = (FNode *)malloc(sizeof(FNode));
    new_node->left = new_node->right = new_node;
    new_node->parent = NULL;
    new_node->child = NULL;
    new_node->key = key;
    new_node->value = value;
    new_node->mark = false;
    new_node->degree = 0;
    return new_node;
}
void free_fnode(FNode* to_free) {
    to_free->degree = -1;
    free(to_free);
}
void kill_fnode(FNode* to_kill) {
    FNode* kid = to_kill->child;
    if (kid) {
        kid->left->right = NULL;
        while (kid->right != NULL) {
            kid = kid->right;
            kill_fnode(kid->left);
        }
        kill_fnode(kid);
    }
    free_fnode(to_kill);
}
void add_fnode(FNode* old, FNode* new_right) {
    FNode* old_right = old->right;
    assert(old != new_right);
    assert(old_right != new_right);
    old->right = new_right;
    old_right->left = new_right;
    new_right->left = old;
    new_right->right = old_right;
}
FHeap* init_fheap(void) { return NULL; }
FElem* add_fheap(FHeap** H, FNode* new_node) {
    assert(H);
    assert(new_node);
    FNode* old_node = *H;
    new_node->parent = NULL;
    new_node->mark = false;
    if (old_node) {
        add_fnode(old_node, new_node);
        if (comp_greater(old_node->key, new_node->key))
            *H = new_node;
    }
    else {
        new_node->left = new_node;
        new_node->right = new_node;
        *H = new_node;
    }
    return new_node;
}
FElem* push_fheap(FHeap** H, Key key, void* value) {
    FNode* new_node = init_fnode(key, value);
    return add_fheap(H, new_node);
}
bool is_empty_fheap(FHeap* H) {
    return H == NULL;
}
data min_fheap(FHeap* H) {
    assert(H);
    data d;
    FNode* head = H;
    d.key = head->key;
    d.value = head->value;
    return d;
}
data elem_data_fheap(FElem* x) {
    assert(x);
    data d;
    d.key = x->key;
    d.value = x->value;
    return d;
}
void remove_from_fheap(FHeap** H, FNode* x) {
    assert(!x->parent);
    if (x->right == x)
        *H = NULL;
    else {
        x->left->right = x->right;
        x->right->left = x->left;
        *H = x->right;
    }
    x->left = x;
    x->right = x;
    x->parent = NULL;
}
FHeap* union_fheap(FHeap* H1, FHeap* H2) {
    if (!H1)
        return H2;
    if (!H2)
        return H1;
    if (comp_less(min_fheap(H2).key, min_fheap(H1).key))
        return union_fheap(H2, H1);
    FNode* H1first = H1;
    FNode* H1last = H1first->left;
    FNode* H2first = H2;
    FNode* H2last = H2first->left;
    H1last->right = H2first;
    H2first->left = H1last;
    H2last->right = H1first;
    H1first->left = H2last;
    return H1first;
}
FNode* link_fheap(FHeap** H, FNode* x, FNode* y) {
    assert(x);
    assert(y);
    assert(x->degree == y->degree);
    if (comp_greater(x->key, y->key))
        return link_fheap(H, y, x);
    remove_from_fheap(H, y);
    if (x->child) {
        FNode* z = x->child;
        y->right = z;
        y->left = z->left;
        z->left->right = y;
        z->left = y;
    }
    y->parent = x;
    x->child = y;
    x->degree++;
    y->mark = false;
    return x;
}
void match_degrees_fheap(FHeap** H, FNode** A, FNode* x) {
    int d = x->degree;
    while (A[d]) {
        if (d > 99)
            exit(1);
        FNode* y = A[d];
        if (y != x) {
            x = link_fheap(H, x, y);
            A[d] = NULL;
            d++;
        }
        else
            break;
    }
    A[d] = x;
}
void consolidate_fheap(FHeap** H) {
    FNode* x = *H;
    if (!x)
        return;
    FNode** A = (FNode**)calloc(100, sizeof(FNode));
    memset(A, '\0', 100);
    assert(x->degree >= 0);
    FNode* last = x->left;
    while(x != last) {
        FNode* next = x->right;
        match_degrees_fheap(H, A, x);
        x = next;
    }
    match_degrees_fheap(H, A, last);
    *H = init_fheap();
    for (int i = 0; i < 100; i++)
        if (A[i])
            add_fheap(H, A[i]);
    free(A);
}
data pop_fheap(FHeap** H) {
    assert(H && *H);
    FNode* z = *H;
    data d = elem_data_fheap(z);
    FNode* first = z->child;
    remove_from_fheap(H, z);
    free_fnode(z);
    if (first) {
        FNode* current = first->right;
        while (current != first) {
            current->parent = NULL;
            current = current->right;
        }
        first->parent = NULL;
        *H = union_fheap(*H, first);
    }
    consolidate_fheap(H);
    return d;
}
void decrease_key_fheap(FHeap** H, FElem* x, Key new_key) {
    assert(H && *H);
    assert(x && comp_gt(x->key, new_key));
    x->key = new_key;
    if (x->parent && comp_greater(x->parent->key, new_key)) {
        if (x->left == x) {
            assert(x->parent->degree == 2);
            x->parent->child = NULL;
        } else {
            assert(x->parent->degree > 2);
            x->left->right = x->right;
            x->right->left = x->left;
            x->parent->child = x->left;
        }
        x->parent->degree--;
        add_fheap(H, x);
        if (! x->parent->mark) {
            x->parent->mark = true;
        } else
            decrease_key_fheap(H, x->parent, x->parent->key);
    } else {
        if (comp_less(new_key, (*H)->key)) {
            assert(!x->parent);
            *H = x;
        }
    }
}
void delete_fheap(FHeap** H, FElem* x) {
    decrease_key_fheap(H, x, (Key){INT_MIN, INT_MIN});
    pop_fheap(H);
}
void free_fheap(FHeap** H) {
    FNode* header = *H;
    FNode* first = header;
    if (header) {
        while(header != first) {
            FNode* next = header->right;
            kill_fnode(header);
            header = next;
        }
    }
    *H = NULL;
}

int main(void) {
    int N;
    scanf("%d", &N);
    int* A = (int *)calloc(N, sizeof(int));
    int* B = (int *)calloc(2 * N, sizeof(int));
    if (A == NULL || B == NULL)
        exit(EXIT_FAILURE);
    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 = 1073741824;
    for (int i = 0; i < N; i++) {
        FHeap* pq = init_fheap();
        for (int j = 0; j < N; j++)
            push_fheap(&pq, (Key){A[j], 0}, NULL);
        for (int j = 0; j < N; j++) {
            data x = pop_fheap(&pq);
            Key a = x.key;
            push_fheap(&pq, (Key){a.fst + B[i + j] / 2, a.snd + 1}, NULL);
        }
        int tmp = 0;
        while (!is_empty_fheap(pq)) {
            data x = pop_fheap(&pq);
            Key a = x.key;
            tmp = tmp > a.snd ? tmp : a.snd;
        }
        m = m < tmp ? m : tmp;
        free_fheap(&pq);
    }
    printf("%d\n", m);
    free(A);
    free(B);
    return 0;
}