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

提出ソース

結果

問題	No.9 モンスターのレベル上げ
ユーザー	magicalkozo
提出日時	2023-09-05 15:41:08
言語	C (gcc 12.3.0)
結果	RE
実行時間	-
コード長	20,238 bytes
コンパイル時間	980 ms
コンパイル使用メモリ	47,544 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-09-05 15:41:14
合計ジャッジ時間	4,892 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
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	RE	-
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: 関数 ‘main’ 内:
main.c:598:17: 警告: 1 番目の ‘rd_int’ の引数へ渡すときに整数からキャスト無しにポインタを作成しています [-Wint-conversion]
  598 |         rd_int(A[i]);
      |                ~^~~
      |                 |
      |                 int
main.c:133:18: 備考: expected ‘int *’ but argument is of type ‘int’
  133 | void rd_int(int *x) { READ_SIGNED }
      |             ~~~~~^
main.c:600:17: 警告: 1 番目の ‘rd_int’ の引数へ渡すときに整数からキャスト無しにポインタを作成しています [-Wint-conversion]
  600 |         rd_int(B[i]);
      |                ~^~~
      |                 |
      |                 int
main.c:133:18: 備考: expected ‘int *’ but argument is of type ‘int’
  133 | void rd_int(int *x) { READ_SIGNED }
      |             ~~~~~^
main.c: トップレベル:
main.c:290:6: 警告: ‘always_inline’ function might not be inlinable [-Wattributes]
  290 | void flush(void) {
      |      ^~~~~
main.c:243:8: 警告: ‘always_inline’ function might not be inlinable [-Wattributes]
  243 | size_t get_integer_size_128(u128 n) {
      |        ^~~~~~~~~~~~~~~~~~~~
main.c:234:8: 警告: ‘always_inline’ function might not be inlinable [-Wattributes]
  234 | size_t get_integer_size_64(u64 n) {
      |        ^~~~~~~~~~~~~~~~~~~
main.c:230:8: 警告: ‘always_inline’ function might not be inlinable [-Wattributes]
  230 | size_t get_integer_size_32(u32 n) {
      |        ^~~~~~~~~~~~~~~~~~~

ソースコード

raw source code

#pragma GCC optimize("O3")
#pragma GCC target("avx512f")
#pragma GCC target("tune=native")
#pragma GCC target("lzcnt")
#pragma GCC target("popcnt")

#include <assert.h>
#include <ctype.h>
#include <inttypes.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>

typedef unsigned uint;
typedef unsigned long long ull;
typedef long long ll;
typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef __int128_t i128;
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __uint128_t u128;
typedef float f32;
typedef double f64;

#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x) , 0)

#define make_tuple2(type_name, type1, type2)                        \
    typedef struct {                                                \
        type1 first;                                                \
        type2 second;                                               \
    } type_name;
#define make_tuple3(type_name, type1, type2, type3)                 \
    typedef struct {                                                \
        type1 first;                                                \
        type2 second;                                               \
        type3 third;                                                \
    } type_name;
#define make_tuple4(type_name, type1, type2, type3, type4)          \
    typedef struct {                                                \
        type1 first;                                                \
        type2 second;                                               \
        type3 third;                                                \
        type4 fourth;                                               \
    } type_name;
#define make_tuple5(type_name, type1, type2, type3, type4, type5)   \
    typedef struct {                                                \
        type1 first;                                                \
        type2 second;                                               \
        type3 third;                                                \
        type4 fourth;                                               \
        type5 fifth;                                                \
    } type_name;
#define make_tuple(a, ...) make_tuple##a(__VA_ARGS__)

// make_tuple(2, Tuple2_i64, i64, i64);
// make_tuple(3, Tuple3_i64, i64, i64, i64);
// make_tuple(4, Tuple4_i64, i64, i64, i64, i64);
// make_tuple(5, Tuple5_i64, i64, i64, i64, i64, i64);

#define ctz32(n) __builtin_ctz((n))
#define ctz64(n) __builtin_ctzll((n))
#define clz32(n) __builtin_clz((n))
#define clz64(n) __builtin_clzll((n))
#define pct32(a) __builtin_popcount((a))
#define pct64(a) __builtin_popcountll((a))
#define ctz(bit_size, n) ((n) ? ctz##bit_size((n)) : bit_size)
#define clz(bit_size, n) ((n) ? clz##bit_size((n)) : bit_size)
#define pct(bit_size, n) (pct##bit_size((n)))
#define msb(bit_size, n) ((n) ? ((bit_size) - (1) - clz(bit_size, (n))) : (0))
#define bit_width(bit_size, n) ((n) ? ((bit_width) - clz(bit_size, (n))) : (0))
#define bit_ceil(bit_size, n) ((!(n)) ? (1) : ((pct(bit_size, n) == (1)) ? ((1) << ((bit_size) - (1) - clz(bit_size, n))) : ((1) << ((bit_size) - clz(bit_size, n)))))
#define bit_floor(bit_size, n) ((!(n)) ? (0) : ((1) << ((bit_size) - (1) - clz(bit_size, (a)))))
#define flip_Nbit(a, n) ((a) ^ ((1) << (n)))
#define only_lsb(a) ((a) & (-(a)))



static char *input_data;
static size_t input_size, input_string_len;

__attribute__((constructor))
void _construct_read_(void) {
    struct stat st;
    fstat(0, &st);
    input_string_len = st.st_size - 1;
    input_size = st.st_size + 1;
    input_data = (char *)mmap(0, input_size, PROT_READ, MAP_PRIVATE, 0, 0);
    // if (unlikely(input_data == MAP_FAILED))
    //     __builtin_trap();
    // madvise(input_data, input_size, MADV_SEQUENTIAL);
}

__attribute__((destructor))
void _destruct_read_(void) {
    munmap(input_data, input_size);
    input_size = input_string_len = 0;
}

#define READ_SKIP                                               \
    char c = *input_data;                                       \
    if (c < '!') *input_data++, c = *input_data;
#define READ_CHAR_TO_INTEGER                                    \
    for (*x = *input_data++ & 15; (c = *input_data++) >= '0';)  \
        *x = *x * 10 + (c & 15);
#define READ_UNSIGNED                                           \
    READ_SKIP                                                   \
    READ_CHAR_TO_INTEGER
#define READ_SIGNED                                             \
    READ_SKIP                                                   \
    bool flag = false;                                          \
    if (c == '-') {                                             \
        flag = true;                                            \
        *input_data++;                                          \
    }                                                           \
    READ_CHAR_TO_INTEGER                                        \
    *x = flag ? (*x) * (-1) : *x;

void rd_int(int *x) { READ_SIGNED }
void rd_ll(ll *x) { READ_SIGNED }
void rd_i32(i32 *x) { READ_SIGNED }
void rd_i64(i64 *x) { READ_SIGNED }
void rd_i128(i128 *x) { READ_SIGNED }
void rd_uint(uint *x) { READ_UNSIGNED }
void rd_ull(ull *x) { READ_UNSIGNED }
void rd_u32(u32 *x) { READ_UNSIGNED }
void rd_u64(u64 *x) { READ_UNSIGNED }
void rd_u128(u128 *x) { READ_UNSIGNED }

#undef READ_SIGNED
#undef READ_UNSIGNED
#undef READ_CHAR_TO_INTEGER
#undef READ_SKIP


#define O_BUF_SIZE 1048576
#define O_BLOCK_SIZE 10000
#define O_INT_SIZE 39

static char output[O_BUF_SIZE + 1];
static char output_block_str[O_BLOCK_SIZE * 4 + 1];
static u128 power10[O_INT_SIZE];
static size_t output_size;

void flush(void);

__attribute__((constructor))
void _construct_write_(void) {
    output_size = 0;
    for (size_t i = 0; i < O_BLOCK_SIZE; i++) {
        size_t j = 4, k = i;
        while (j--) {
            output_block_str[i * 4 + j] = k % 10 + '0';
            k /= 10;
        }
    }
    power10[0] = 1ull;
    for (size_t i = 1; i < O_INT_SIZE; i++)
        power10[i] = power10[i - 1] * 10;
}

__attribute__((destructor))
void _destruct_write_(void) {
    flush();
    output_size = 0;
}

#define DIGIT_BLOCK1                                            \
    if (n >= power10[9]) return 10;                             \
    if (n >= power10[8]) return 9;                              \
    if (n >= power10[7]) return 8;                              \
    if (n >= power10[6]) return 7;                              \
    if (n >= power10[5]) return 6;                              \
    if (n >= power10[4]) return 5;                              \
    if (n >= power10[3]) return 4;                              \
    if (n >= power10[2]) return 3;                              \
    if (n >= power10[1]) return 2;                              \
    return 1;

#define DIGIT_BLOCK2                                            \
    if (n >= power10[19]) return 20;                            \
    if (n >= power10[18]) return 19;                            \
    if (n >= power10[17]) return 18;                            \
    if (n >= power10[16]) return 17;                            \
    if (n >= power10[15]) return 16;                            \
    if (n >= power10[14]) return 15;                            \
    if (n >= power10[13]) return 14;                            \
    if (n >= power10[12]) return 13;                            \
    if (n >= power10[11]) return 12;                            \
    return 11;

#define DIGIT_BLOCK3                                            \
    if (n >= power10[29]) return 30;                            \
    if (n >= power10[28]) return 29;                            \
    if (n >= power10[27]) return 28;                            \
    if (n >= power10[26]) return 27;                            \
    if (n >= power10[25]) return 26;                            \
    if (n >= power10[24]) return 25;                            \
    if (n >= power10[23]) return 24;                            \
    if (n >= power10[22]) return 23;                            \
    if (n >= power10[21]) return 22;                            \
    return 21;

#define DIGIT_BLOCK4                                            \
    if (n >= power10[38]) return 39;                            \
    if (n >= power10[37]) return 38;                            \
    if (n >= power10[36]) return 37;                            \
    if (n >= power10[35]) return 36;                            \
    if (n >= power10[34]) return 35;                            \
    if (n >= power10[33]) return 34;                            \
    if (n >= power10[32]) return 33;                            \
    if (n >= power10[31]) return 32;                            \
    return 31;

__attribute__((always_inline))
size_t get_integer_size_32(u32 n) {
    DIGIT_BLOCK1
}
__attribute__((always_inline))
size_t get_integer_size_64(u64 n) {
    if (n >= power10[10]) {
        DIGIT_BLOCK2
    }
    else {
        DIGIT_BLOCK1
    }
}
__attribute__((always_inline))
size_t get_integer_size_128(u128 n) {
    if (n >= power10[30]) {
        DIGIT_BLOCK4
    }
    else if (n >= power10[20]) {
        DIGIT_BLOCK3
    }
    else if (n >= power10[10]) {
        DIGIT_BLOCK2
    }
    else {
        DIGIT_BLOCK1
    }
}

#define OUTPUT_BUFFER_EQ_CHECK                                  \
    if (unlikely(output_size == O_BUF_SIZE))                    \
        flush();

#define OUTPUT_BUFFER_CHECK                                     \
    if (unlikely(output_size + O_INT_SIZE >= O_BUF_SIZE))       \
        flush();

#define WRITE_PER_4CHARS(bit)                                                                   \
    size_t digit = get_integer_size_##bit(x);                                                   \
    size_t len = digit;                                                                         \
    while (len >= 4) {                                                                          \
        len -= 4;                                                                               \
        memcpy(output + output_size + len, output_block_str + (x % O_BLOCK_SIZE) * 4, 4);       \
        x /= O_BLOCK_SIZE;                                                                      \
    }                                                                                           \
    memcpy(output + output_size, output_block_str + x * 4 + (4 - len), len);                    \
    output_size += digit;

#define WRITE_UNSIGNED(bit)                                                                     \
    OUTPUT_BUFFER_CHECK                                                                         \
    WRITE_PER_4CHARS(bit)

#define WRITE_SIGNED(bit)                                                                       \
    OUTPUT_BUFFER_CHECK                                                                         \
    if (x < 0) {                                                                                \
        output[output_size++] = '-';                                                            \
        x = -x;                                                                                 \
    }                                                                                           \
    WRITE_PER_4CHARS(bit)

__attribute__((always_inline))
void flush(void) {
    fwrite(output, 1, output_size, stdout);
    output_size = 0;
}

void wt_char(char c) {
    output[output_size++] = c;
    OUTPUT_BUFFER_EQ_CHECK
}
void wt_str(const char* s) {
    while (*s != 0) {
        output[output_size++] = *s++;
        OUTPUT_BUFFER_EQ_CHECK
    }
}
void wt_uint(uint x) { WRITE_UNSIGNED(32) }
void wt_ull(ull x) { WRITE_UNSIGNED(64) }
void wt_u32(u32 x) { WRITE_UNSIGNED(32) }
void wt_u64(u64 x) { WRITE_UNSIGNED(64) }
void wt_u128(u128 x) { WRITE_UNSIGNED(128) }
void wt_int(int x) { WRITE_SIGNED(32) }
void wt_ll(ll x) { WRITE_SIGNED(64) }
void wt_i32(i32 x) { WRITE_SIGNED(32) }
void wt_i64(i64 x) { WRITE_SIGNED(64) }
void wt_i128(i128 x) { WRITE_SIGNED(128) }

#undef WRITE_SIGNED
#undef WRITE_UNSIGNED
#undef WRITE_PER_4CHARS
#undef OUTPUT_BUFFER_CHECK
#undef OUTPUT_BUFFER_EQ_CHECK
#undef DIGIT_BLOCK4
#undef DIGIT_BLOCK3
#undef DIGIT_BLOCK2
#undef DIGIT_BLOCK1
#undef O_BUF_SIZE
#undef O_BLOCK_SIZE
#undef O_INT_SIZE


#define rd(type, x) \
    type x;         \
    rd_##type(&x)
#define wt(type, x) \
    wt_##type((x))


make_tuple2(Key, int, int);
make_tuple2(Data, Key, void*);


bool comp_g(Key a, Key b) { return a.first == b.first ? a.second > b.second : a.first > b.first; }
bool comp_gt(Key a, Key b) { return a.first == b.first ? a.second >= b.second : a.first >= b.first; }
bool comp_l(Key a, Key b) { return a.first == b.first ? a.second < b.second : a.first < b.first; }
bool comp_lt(Key a, Key b) { return a.first == b.first ? a.second <= b.second : a.first <= b.first; }
bool comp_e(Key a, Key b) { return a.first == b.first && a.second == b.second; }

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_g(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.first = head->key;
    d.second = head->value;
    return d;
}
Data elem_data_fheap(FElem* x) {
    assert(x);
    Data d;
    d.first = x->key;
    d.second = 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_l(min_fheap(H2).first, min_fheap(H1).first))
        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_g(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_g(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_l(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) {
    rd(int, N);
    int *A = (int *)calloc(N, sizeof(int));
    int *B = (int *)calloc(2 * N, sizeof(int));
    if (unlikely(A == NULL))
        exit(EXIT_FAILURE);
    if (unlikely(B == NULL))
        exit(EXIT_FAILURE);
    for (int i = 0; i < N; i++)
        rd_int(A[i]);
    for (int i = 0; i < N; i++) {
        rd_int(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.first;
            push_fheap(&pq, (Key){a.first + B[i + j] / 2, a.second + 1}, NULL);
        }
        int tmp = 0;
        while (!is_empty_fheap(pq)) {
            Data x = pop_fheap(&pq);
            Key a = x.first;
            tmp = tmp > a.second ? tmp : a.second;
        }
        m = m < tmp ? m : tmp;
    }
    wt(int, m);
    free(A);
    free(B);
    return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード