結果

問題 No.3 ビットすごろく
ユーザー magicalkozomagicalkozo
提出日時 2023-08-11 21:40:20
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 7,111 bytes
コンパイル時間 532 ms
コンパイル使用メモリ 34,664 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-11 21:40:24
合計ジャッジ時間 2,899 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 0 ms
4,380 KB
testcase_02 AC 0 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 3 ms
4,376 KB
testcase_15 AC 3 ms
4,376 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 3 ms
4,380 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 3 ms
4,376 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 0 ms
4,380 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 3 ms
4,380 KB
testcase_24 AC 3 ms
4,380 KB
testcase_25 AC 3 ms
4,376 KB
testcase_26 AC 0 ms
4,376 KB
testcase_27 AC 1 ms
4,376 KB
testcase_28 AC 3 ms
4,376 KB
testcase_29 AC 2 ms
4,376 KB
testcase_30 AC 0 ms
4,376 KB
testcase_31 AC 0 ms
4,376 KB
testcase_32 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: 関数 ‘main’ 内:
main.c:267:28: 警告: 3 番目の ‘fib_heap_insert’ の引数へ渡すときに整数からキャスト無しにポインタを作成しています [-Wint-conversion]
  267 |     fib_heap_insert(&q, i, 1);
      |                            ^
      |                            |
      |                            int
main.c:87:54: 備考: expected ‘void *’ but argument is of type ‘int’
   87 | FibElem* fib_heap_insert(FibHeap** H, int key, void* value) {
      |                                                ~~~~~~^~~~~
main.c:270:21: 警告: ポインタと整数との比較を行なっています
  270 |         if (v.value == N) {
      |                     ^~
main.c:271:30: 警告: ポインタから異なるサイズの整数へのキャストです [-Wpointer-to-int-cast]
  271 |             printf("%d\n", d[(int)v.value]);
      |                              ^
main.c:275:37: 警告: passing argument 1 番目の ‘__builtin_popcount’ の引数を渡すときにポインタからキャスト無しに整数を作成しています [-Wint-conversion]
  275 |         int b = __builtin_popcount(v.value);
      |                                    ~^~~~~~
      |                                     |
      |                                     void *
main.c:275:37: 備考: expected ‘unsigned int’ but argument is of type ‘void *’
main.c:276:17: 警告: initialization of ‘int’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
  276 |         int a = v.value + b;
      |                 ^
main.c:277:17: 警告: initialization of ‘int’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
  277 |         int c = v.value - b;
      |                 ^
main.c:279:22: 警告: ポインタから異なるサイズの整数へのキャストです [-Wpointer-to-int-cast]
  279 |             d[a] = d[(int)v.value] + 1;
      |                      ^
main.c:2

ソースコード

diff # 

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

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

typedef struct FibNode FibNode;

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

typedef FibNode FibHeap;
typedef FibNode FibElem;

FibNode* fib_node_init(int key, void* value) {
    FibNode* new_node = (FibNode *)malloc(sizeof(FibNode));
    new_node->left = new_node->right = new_node;
    new_node->key = key;
    new_node->value = value;
    new_node->parent = NULL;
    new_node->child = NULL;
    new_node->mark = false;
    new_node->degree = 0;
    return new_node;
}
void fib_node_free(FibNode* to_free) {
    to_free->degree = -1;
    free(to_free);
}
void fib_node_kill(FibNode* to_kill) {
    FibNode* kid = to_kill->child;
    if (kid) {
        kid->left->right = NULL;
        while (kid->right != NULL) {
            kid = kid->right;
            fib_node_kill(kid->left);
        }
        fib_node_kill(kid);
    }
    fib_node_free(to_kill);
}
void fib_node_add(FibNode* old, FibNode* new_right) {
    FibNode* oldRight = old->right;
    assert(old != new_right);
    assert(oldRight != new_right);
    old->right = new_right;
    oldRight->left = new_right;
    new_right->left = old;
    new_right->right = oldRight;
}
FibHeap* fib_heap_init(void) {
    return NULL;
}
FibElem* fib_heap_add(FibHeap** H, FibNode* new_node) {
    assert(H);
    assert(new_node);
    FibNode* old_node = *H;
    new_node->parent = NULL;
    new_node->mark = false;
    if (old_node) {
        fib_node_add(old_node, new_node);
        if (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;
}
FibElem* fib_heap_insert(FibHeap** H, int key, void* value) {
    FibNode* new_node = fib_node_init(key, value);
    return fib_heap_add(H, new_node);
}
bool is_empty_fib_heap(FibHeap* H) {
    return H == NULL;
}
data fib_heap_min(FibHeap* H) {
    assert(H);
    data d;
    FibNode* head = H;
    d.key = head->key;
    d.value = head->value;
    return d;
}
data fib_heap_elem_data(FibElem* x) {
    assert(x);
    data d;
    d.key = x->key;
    d.value = x->value;
    return d;
}
void fib_heap_remove_from(FibHeap** H, FibNode* 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;
}
FibHeap* fib_heap_union(FibHeap* H1, FibHeap* H2) {
    if (!H1)
        return H2;
    if (!H2)
        return H1;
    if (fib_heap_min(H2).key < fib_heap_min(H1).key)
        return fib_heap_union(H2, H1);
    FibNode* H1first = H1;
    FibNode* H1last = H1first->left;
    FibNode* H2first = H2;
    FibNode* H2last = H2first->left;
    H1last->right = H2first;
    H2first->left = H1last;
    H2last->right = H1first;
    H1first->left = H2last;
    return H1first;
}
FibNode* fib_heap_link(FibHeap** H, FibNode* x, FibNode* y) {
    assert(x);
    assert(y);
    assert(x->degree == y->degree);
    if (x->key > y->key)
        return fib_heap_link(H, y, x);
    fib_heap_remove_from(H, y);
    if (x->child) {
        FibNode* 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 fib_heap_match_degrees(FibHeap** H, FibNode** A, FibNode* x) {
    int d = x->degree;
    while (A[d]) {
        if (d > 99)
            exit(1);
        FibNode* y = A[d];
        if (y != x) {
            x = fib_heap_link(H, x, y);
            A[d] = NULL;
            d++;
        }
        else
            break;
    }
    A[d] = x;
}
void fib_heap_consolidate(FibHeap** H) {
    FibNode* x = *H;
    if (!x)
        return;
    FibNode** A = (FibNode**)calloc(100, sizeof(FibNode));
    memset(A, '\0', 100);
    assert(x->degree >= 0);
    FibNode* last = x->left;
    while(x != last) {
        FibNode* next = x->right;
        fib_heap_match_degrees(H, A, x);
        x = next;
    }
    fib_heap_match_degrees(H, A, last);
    *H = fib_heap_init();
    for (int i=0; i<100; i++)
        if (A[i])
            fib_heap_add(H, A[i]);
    free(A);
}
data fib_heap_extract_min(FibHeap** H) {
    assert(H && *H);
    FibNode* z = *H;
    data d = fib_heap_elem_data(z);
    FibNode* first = z->child;
    fib_heap_remove_from(H, z);
    fib_node_free(z);
    if (first) {
        FibNode* current = first->right;
        while (current != first) {
            current->parent = NULL;
            current = current->right;
        }
        first->parent = NULL;
        *H = fib_heap_union(*H, first);
    }
    fib_heap_consolidate(H);
    return d;
}
void fib_heap_decrease_key(FibHeap** H, FibElem* x, int new_key) {
    assert(H && *H);
    assert(x && x->key >= new_key);
    x->key = new_key;
    if (x->parent && 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--;
        fib_heap_add(H, x);
        if (! x->parent->mark) {
            x->parent->mark = true;
        } else
            fib_heap_decrease_key(H, x->parent, x->parent->key);
    } else {
        if (new_key < (*H)->key) {
            assert(!x->parent);
            *H = x;
        }
    }
}
void fib_heap_delete(FibHeap** H, FibElem* x) {
    fib_heap_decrease_key(H, x, INT_MIN);
    fib_heap_extract_min(H);
}
void fib_heap_free(FibHeap** H) {
    FibNode* header = *H;
    FibNode* first = header;
    if (header) {
        while(header != first) {
            FibNode* next = header->right;
            fib_node_kill(header);
            header = next;
        }
    }
    *H = NULL;
}

int main(void) {
    int N;
    scanf("%d", &N);
    int* d = (int *)calloc(N + 1, sizeof(int));
    if (d == NULL)
        exit(EXIT_FAILURE);
    d[1] = 1;
    FibHeap *q = fib_heap_init();
    int i = 1;
    fib_heap_insert(&q, i, 1);
    while (!is_empty_fib_heap(q)) {
        data v = fib_heap_extract_min(&q);
        if (v.value == N) {
            printf("%d\n", d[(int)v.value]);
            free(d);
            return 0;
        }
        int b = __builtin_popcount(v.value);
        int a = v.value + b;
        int c = v.value - b;
        if (a <= N && d[a] == 0) {
            d[a] = d[(int)v.value] + 1;
            fib_heap_insert(&q, ++i, a);
        }
        if (c > 0 && d[c] == 0) {
            d[c] = d[(int)v.value] + 1;
            fib_heap_insert(&q, ++i, c);
        }
    }
    printf("-1\n");
    free(d);
    return 0;
}
0