#699671 (C) No.50 おもちゃ箱

提出ソース

結果

問題	No.50 おもちゃ箱
ユーザー	kaoru murata
提出日時	2021-09-15 03:16:00
言語	C (gcc 12.3.0)
結果	WA
実行時間	-
コード長	5,380 bytes
コンパイル時間	266 ms
コンパイル使用メモリ	33,920 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-27 23:29:29
合計ジャッジ時間	1,469 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	AC	1 ms 5,376 KB
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	AC	1 ms 5,376 KB
testcase_09	WA	-
testcase_10	WA	-
testcase_11	AC	1 ms 5,376 KB
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	AC	1 ms 5,376 KB
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	AC	1 ms 5,376 KB
testcase_24	AC	1 ms 5,376 KB
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	1 ms 5,376 KB
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	AC	1 ms 5,376 KB
testcase_36	WA	-
testcase_37	AC	2 ms 5,376 KB
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.c: In function 'in':
main.c:36:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
   36 |   while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f;
      |              ^~~~~~~~~~~~~~~~
main.c: In function 'out':
main.c:55:5: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration]
   55 |     putchar_unlocked('-');
      |     ^~~~~~~~~~~~~~~~
main.c: In function 'main':
main.c:188:11: warning: passing argument 1 of 'radix32' from incompatible pointer type [-Wincompatible-pointer-types]
  188 |   radix32(B, M);
      |           ^
      |           |
      |           u64 * {aka long unsigned int *}
main.c:110:26: note: expected 'i32 *' {aka 'int *'} but argument is of type 'u64 *' {aka 'long unsigned int *'}
  110 | static void radix32(i32 *a, const i32 sz) {
      |                     ~~~~~^

ソースコード

raw source code

#include <assert.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#pragma region typedef
/* signed integer */
typedef   int8_t      i8;
typedef   int16_t     i16;
typedef   int32_t     i32;
typedef   int64_t     i64;
typedef __int128_t    i128;

/* unsigned integer */
typedef   uint8_t     u8;
typedef   uint16_t    u16;
typedef   uint32_t    u32;
typedef   uint64_t    u64;
typedef __uint128_t   u128;

/* floating point number */
typedef   float       f32;
typedef   double      f64;
typedef   long double f80;
#pragma endregion typedef

#pragma region io
static inline i64 in(void) {
  i64 x = 0;
  i64 f = 1;
  i64 c;
  while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f;
  while (47 < c && c < 58) {
    x = x * 10 + c - 48;
    c = getchar_unlocked();
  }
  return f * x;
}
static inline u64 inU(void) {
  u64 x = 0;
  u64 c;
  while (c = getchar_unlocked(), c < 48 || c > 57);
  while (47 < c && c < 58) {
    x = x * 10 + c - 48;
    c = getchar_unlocked();
  }
  return x;
}
static inline void out(i64 x) {
  if (x < 0) {
    putchar_unlocked('-');
    x = -x;
  }
  if (x >= 10) out(x / 10);
  putchar_unlocked(x - x / 10 * 10 + 48);
}
static inline void outU(u64 x) {
  if (x >= 10) outU(x / 10);
  putchar_unlocked(x - x / 10 * 10 + 48);
}
static inline void nl(void) { putchar_unlocked('\n'); }
static inline void sp(void) { putchar_unlocked(' '); }
#pragma endregion io

#pragma region montgomery form
static inline u64 _inv(u64 mod) {
  int i;
  u64 u = 1;
  u64 v = 0;
  u64 x = 1ULL << 63;
  for (int i = 0; i < 64; i++) {
    if (u & 1){
      u = (u + mod) / 2;
      v = v / 2 + x;
    } else {
      u >>= 1;
      v >>= 1;
    }
  }
  return -v;
}
static inline u64 _one(u64 mod) { return -1ULL % mod + 1; }
static inline u64 _r2(u64 mod) { return (u128) (i128) -1 % mod + 1; }
static inline u64 _MR(u128 x, u64 inv, u64 mod) {
    i64 z = (x >> 64) - ((((u64)x * inv) * (u128)mod) >> 64);
    return z < 0 ? z + mod : z;
}
static inline u64 to_montgomery_form(u64 a, u64 r2, u64  inv, u64 mod) { return _MR((u128)a * r2, inv, mod); }
static inline u64 from_montgomery_form(u64 a, u64 inv, u64 mod) { return _MR((u128)a, inv, mod); }
static inline u64 addmod64(u64 x, u64 y, u64 mod) { return x + y >= mod ? x + y - mod : x + y; }
static inline u64 submod64(u64 x, u64 y, u64 mod) { return x >= y  ? x - y : x - y + mod; }
static inline u64 mulmod64(u64 x, u64 y, u64 r2, u64 inv, u64 mod) { return _MR((u128)r2 * _MR((u128)x * y, inv, mod), inv, mod); }
static inline u64 powmod64(u64 a, u64 n, u64 r2, u64 inv, u64 mod) {
  u64 res = _one(mod);
  u64 A = to_montgomery_form(a, r2, inv, mod);
  while (n > 0) {
    if (n & 1) res = _MR((u128)res * A, inv, mod);
    A = _MR((u128)A * A, inv, mod);
    n >>= 1;
  }
  return from_montgomery_form(res, inv, mod);
}
#pragma endregion montgomery form

#pragma region radix sort
static void radix32(i32 *a, const i32 sz) {
  i32 shift = 0;
  i32 elem[0x100];
  i32 *aux = (i32 *)malloc(sizeof(i32) * sz);
  i64 x = 0;
  if (aux == NULL) { exit(EXIT_FAILURE); }
  while (shift < 32) {
    i32 bucket[0x100] = {0};
    for (i32 i = 0; i < sz; i++) {
      x = (a[i] >> shift) & 0xff;
      bucket[x]++;
      aux[i] = a[i];
    }
    elem[0] = 0;
    for (i32 i = 0; i < 0xff; i++) { elem[i + 1] = elem[i] + bucket[i]; }
    for (i32 i = 0; i < sz; i++) {
      x = (aux[i] >> shift) & 0xff;
      a[elem[x]] = aux[i];
      elem[x]++;
    }
    shift += 8;
  }
  free(aux);
}
static void radix64(i64 *a, const i64 sz, const i64 minus) {
  i64 shift = 0;
  i64 sw = 0;
  i64 elem[0x10000];
  i64 *aux = (i64 *)malloc(sizeof(i64) * sz);
  i128 x = 0;
  if (aux == NULL) { exit(EXIT_FAILURE); }
  while (shift < 64) {
    i64 bucket[0x10000] = {0};
    for (i64 i = 0; i < sz; i++) {
      x = (a[i] >> shift) & 0xffff;
      bucket[x]++;
      aux[i] = a[i];
    }
    elem[0] = 0;
    for (i64 i = 0; i < 0xffff; i++) { elem[i + 1] = elem[i] + bucket[i]; }
    for (i64 i = 0; i < sz; i++) {
      x = (aux[i] >> shift) & 0xffff;
      a[elem[x]] = aux[i];
      elem[x]++;
    }
    shift += 16;
  }
  free(aux);
  for (i64 i = 0; i < (minus >> 1); i++) {
    sw = a[sz - minus + i];
    a[sz - minus + i] = a[sz - 1 - i];
    a[sz - 1 - i] = sw;
  }
  for (i64 i = 0; i < ((sz - minus) >> 1); i++) {
    sw = a[i];
    a[i] = a[sz - minus - 1 - i];
    a[sz - minus - 1 - i] = sw;
  }
  for (i64 i = 0; i < (sz >> 1); i++) {
    sw = a[i];
    a[i] = a[sz - 1 - i];
    a[sz - 1 - i] = sw;
  }
}
#pragma endregion radix sort

#define INF 1234567

bool dp1[1<<10];
bool dp2[1<<10];

int main() {
  u64 u;
  u64 A[11], B[11];
  u64 N = inU();
  for (u = 0; u < N; u++) A[u] = in();
  u64 M = inU();
  for (u = 0; u < M; u++) B[u] = in();
  radix32(B, M);
  dp1[0] = true;
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < (1 << N); j++) {
      int c = 0;
      for (int k = 0; k < N; k++) {
        if ((j >> k) % 2 == 0) continue;
        c += A[k];
      }
      if (c > B[M - 1 - i]) continue;
      for (int k = (1 << N) - 1; k >= 0; k--) {
        dp2[j | k] |= dp1[k];
      }
      for (int k = (1 << N) - 1; k >= 0; k--) {
        dp1[k] = dp2[k];
      }
      if (dp1[(1 << N) - 1]) {
        out(i + 1);
        nl();
        return 0;
      }
    }
  }
  out(-1);
  nl();
  return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード