結果

問題 No.50 おもちゃ箱
コンテスト
ユーザー kaoru murata
提出日時 2021-09-15 03:11:37
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,800 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 819 ms
コンパイル使用メモリ 33,920 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-27 23:23:24
合計ジャッジ時間 1,362 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 3
other AC * 3 WA * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in':
main.c:28:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
   28 |   while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f;
      |              ^~~~~~~~~~~~~~~~
main.c: In function 'out':
main.c:47:5: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration]
   47 |     putchar_unlocked('-');
      |     ^~~~~~~~~~~~~~~~
main.c: In function 'main':
main.c:142:11: warning: passing argument 1 of 'radix32' from incompatible pointer type [-Wincompatible-pointer-types]
  142 |   radix32(B, M);
      |           ^
      |           |
      |           u64 * {aka long unsigned int *}
main.c:61:26: note: 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: warning: passing argument 1 of 'rev' from incompatible pointer type [-Wincompatible-pointer-types]
  143 |   rev(B, M);
      |       ^
      |       |
      |       u64 * {aka long unsigned int *}
main.c:126:15: note: expected 'i32 *' {aka 'int *'} but argument is of type 'u64 *' {aka 'long unsigned int *'}
  126 | void rev(i32 *a, const i32 sz) {
      |          ~~~~~^

ソースコード

diff #
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>

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