結果

問題 No.50 おもちゃ箱
ユーザー kaoru muratakaoru murata
提出日時 2021-09-15 03:11:37
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 3,800 bytes
コンパイル時間 1,095 ms
コンパイル使用メモリ 32,140 KB
実行使用メモリ 5,316 KB
最終ジャッジ日時 2023-09-10 07:52:37
合計ジャッジ時間 1,863 ms
ジャッジサーバーID
(参考情報)
judge12 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 1 ms
4,376 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 1 ms
4,380 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 1 ms
4,376 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: 関数 ‘in’ 内:
main.c:28:14: 警告: 関数 ‘getchar_unlocked’ の暗黙的な宣言です [-Wimplicit-function-declaration]
   28 |   while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f;
      |              ^~~~~~~~~~~~~~~~
main.c: 関数 ‘out’ 内:
main.c:47:5: 警告: 関数 ‘putchar_unlocked’ の暗黙的な宣言です [-Wimplicit-function-declaration]
   47 |     putchar_unlocked('-');
      |     ^~~~~~~~~~~~~~~~
main.c: 関数 ‘main’ 内:
main.c:142:11: 警告: 互換性のないポインタ型から 1 番目の ‘radix32’ の引数に渡しています [-Wincompatible-pointer-types]
  142 |   radix32(B, M);
      |           ^
      |           |
      |           u64 * {aka long unsigned int *}
main.c:61:26: 備考: expected ‘i32 *’ {aka ‘int *’} but argument is of type ‘u64 *’ {aka ‘long unsigned int *’}
   61 | static void radix32(i32 *a, const i32 sz) {
      |                     ~~~~~^
main.c:143:7: 警告: 互換性のないポインタ型から 1 番目の ‘rev’ の引数に渡しています [-Wincompatible-pointer-types]
  143 |   rev(B, M);
      |       ^
      |       |
      |       u64 * {aka long unsigned int *}
main.c:126:15: 備考: expected ‘i32 *’ {aka ‘int *’} but argument is of type ‘u64 *’ {aka ‘long unsigned int *’}
  126 | void rev(i32 *a, const i32 sz) {
      |          ~~~~~^

ソースコード

diff #

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

/* 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;

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(' '); }


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;
  }
}

void rev(i32 *a, const i32 sz) {
  for (int i = 0; i < (sz >> 1); i++) {
    a[i] ^= a[sz - i] ^= a[i] ^= a[sz - i];
  }
}

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);
  rev(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[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;
}
0