結果

問題 No.206 数の積集合を求めるクエリ
ユーザー Min_25Min_25
提出日時 2015-05-09 11:12:11
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 471 ms / 7,000 ms
コード長 1,712 bytes
コンパイル時間 101 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 28,536 KB
最終ジャッジ日時 2024-07-05 21:10:18
合計ジャッジ時間 7,285 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
10,624 KB
testcase_01 AC 35 ms
10,624 KB
testcase_02 AC 32 ms
10,752 KB
testcase_03 AC 32 ms
10,624 KB
testcase_04 AC 32 ms
10,752 KB
testcase_05 AC 31 ms
10,752 KB
testcase_06 AC 35 ms
11,392 KB
testcase_07 AC 34 ms
11,392 KB
testcase_08 AC 37 ms
11,136 KB
testcase_09 AC 36 ms
11,136 KB
testcase_10 AC 31 ms
10,752 KB
testcase_11 AC 33 ms
10,752 KB
testcase_12 AC 37 ms
11,392 KB
testcase_13 AC 36 ms
11,264 KB
testcase_14 AC 36 ms
11,136 KB
testcase_15 AC 35 ms
11,008 KB
testcase_16 AC 35 ms
11,136 KB
testcase_17 AC 448 ms
27,564 KB
testcase_18 AC 411 ms
28,400 KB
testcase_19 AC 437 ms
27,624 KB
testcase_20 AC 135 ms
20,900 KB
testcase_21 AC 327 ms
25,524 KB
testcase_22 AC 295 ms
25,060 KB
testcase_23 AC 442 ms
28,304 KB
testcase_24 AC 471 ms
27,528 KB
testcase_25 AC 452 ms
26,860 KB
testcase_26 AC 439 ms
28,536 KB
testcase_27 AC 312 ms
23,720 KB
testcase_28 AC 405 ms
26,364 KB
testcase_29 AC 415 ms
26,124 KB
testcase_30 AC 318 ms
24,280 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def ilog2(n):
  if n <= 0:
    return 0
  else:
    return n.bit_length() - 1

def _pack(pack, shamt):
  size = len(pack)
  while size > 1:
    npack = []
    for i in range(0, size - 1, 2):
      npack.append(pack[i] | (pack[i+1] << shamt))
    if size & 1:
      npack.append(pack[-1])
    pack = npack
    size = (size + 1) >> 1
    shamt <<= 1
  return pack[0]

def _pack2(seq1, seq2, shamt):
  M1 = _pack(seq1, shamt)
  M2 = _pack(seq2, shamt)
  size = len(seq1) + len(seq2) - 1
  block_size = 1 << ilog2(size - 1)
  return M1, M2, shamt * block_size

def pack_sequence2_mod(seq1, seq2, mod):
  size = min(len(seq1), len(seq2))
  max_value = (mod - 1) ** 2 * size
  shamt = max_value.bit_length()
  return _pack2(seq1, seq2, shamt)

def unpack_sequence(M, size, shamt):
  needed_sizes = []
  s = size
  while s > 1:
    needed_sizes.append(s)
    s = (s + 1) >> 1
  ret = [M]
  for needed_size in needed_sizes[::-1]:
    mask = (1 << shamt) - 1
    nret = []
    for c in ret:
      nret.append(c & mask)
      nret.append(c >> shamt)
    ret = nret[:needed_size]
    shamt >>= 1
  return ret

def poly_mul_mod_builtin(poly1, poly2, mod):
  M1, M2, shamt = pack_sequence2_mod(poly1, poly2, mod)
  size = len(poly1) + len(poly2) - 1
  seq = unpack_sequence(M1 * M2, size, shamt)
  return seq # x % mod

def solve():
  stdin = sys.stdin
  write = sys.stdout.write

  _, _, N = map(int, stdin.readline().split())
  A = [0] * (N + 1)
  B = [0] * (N + 1)
  for n in map(int, stdin.readline().split()):
    A[n] = 1
  for n in map(int, stdin.readline().split()):
    B[N - n] = 1
  Q = int(stdin.readline())
  C = poly_mul_mod_builtin(A, B, 2)
  write("%s\n" % "\n".join(map(str, C[N:N+Q])))

solve()
0