結果
| 問題 |
No.9 モンスターのレベル上げ
|
| ユーザー |
 magicalkozo
|
| 提出日時 | 2023-09-05 15:41:33 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 2,271 ms / 5,000 ms |
| コード長 | 20,240 bytes |
| コンパイル時間 | 1,540 ms |
| コンパイル使用メモリ | 48,884 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-06-23 11:14:10 |
| 合計ジャッジ時間 | 22,396 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 |
コンパイルメッセージ
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) {
| ^~~~~~~~~~~~~~~~~~~
ソースコード
#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;
}