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

提出ソース

結果

問題	No.9 モンスターのレベル上げ
ユーザー	magicalkozo
提出日時	2023-09-05 15:41:08
言語	C (gcc 12.3.0)
結果	RE
実行時間	-
コード長	20,238 bytes
コンパイル時間	1,164 ms
コンパイル使用メモリ	48,612 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-06-23 11:13:22
合計ジャッジ時間	4,339 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
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: In function 'main':
main.c:598:17: warning: passing argument 1 of 'rd_int' makes pointer from integer without a cast [-Wint-conversion]
  598 |         rd_int(A[i]);
      |                ~^~~
      |                 |
      |                 int
main.c:133:18: note: expected 'int *' but argument is of type 'int'
  133 | void rd_int(int *x) { READ_SIGNED }
      |             ~~~~~^
main.c:600:17: warning: passing argument 1 of 'rd_int' makes pointer from integer without a cast [-Wint-conversion]
  600 |         rd_int(B[i]);
      |                ~^~~
      |                 |
      |                 int
main.c:133:18: note: expected 'int *' but argument is of type 'int'
  133 | void rd_int(int *x) { READ_SIGNED }
      |             ~~~~~^
main.c: At top level:
main.c:290:6: warning: 'always_inline' function might not be inlinable [-Wattributes]
  290 | void flush(void) {
      |      ^~~~~
main.c:243:8: warning: 'always_inline' function might not be inlinable [-Wattributes]
  243 | size_t get_integer_size_128(u128 n) {
      |        ^~~~~~~~~~~~~~~~~~~~
main.c:234:8: warning: 'always_inline' function might not be inlinable [-Wattributes]
  234 | size_t get_integer_size_64(u64 n) {
      |        ^~~~~~~~~~~~~~~~~~~
main.c:230:8: warning: '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

結果

テストケース

コンパイルメッセージ

ソースコード