#961071 (Nim) No.2672 Subset Xor Sum

• 問題: No.2672 Subset Xor Sum
• ユーザー: 寝癖
• 提出日時: 2024-03-15 23:46:46
• 言語: Nim (2.0.2)
• 結果: AC
• 実行時間: 70 ms / 2,000 ms
• コード長: 6,929 bytes
• コンパイル時間: 4,886 ms
• コンパイル使用メモリ: 78,548 KB
• 実行使用メモリ: 7,352 KB
• 最終ジャッジ日時: 2024-03-16 17:43:26
• 合計ジャッジ時間: 7,611 ms
• ジャッジサーバーID （参考情報）: judge14 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,676 KB
testcase_01	AC	1 ms; 6,676 KB
testcase_02	AC	2 ms; 6,676 KB
testcase_03	AC	2 ms; 6,676 KB
testcase_04	AC	2 ms; 6,676 KB
testcase_05	AC	2 ms; 6,676 KB
testcase_06	AC	2 ms; 6,676 KB
testcase_07	AC	2 ms; 6,676 KB
testcase_08	AC	2 ms; 6,676 KB
testcase_09	AC	2 ms; 6,676 KB
testcase_10	AC	2 ms; 6,676 KB
testcase_11	AC	2 ms; 6,676 KB
testcase_12	AC	2 ms; 6,676 KB
testcase_13	AC	2 ms; 6,676 KB
testcase_14	AC	2 ms; 6,676 KB
testcase_15	AC	2 ms; 6,676 KB
testcase_16	AC	2 ms; 6,676 KB
testcase_17	AC	2 ms; 6,676 KB
testcase_18	AC	2 ms; 6,676 KB
testcase_19	AC	2 ms; 6,676 KB
testcase_20	AC	2 ms; 6,676 KB
testcase_21	AC	2 ms; 6,676 KB
testcase_22	AC	2 ms; 6,676 KB
testcase_23	AC	2 ms; 6,676 KB
testcase_24	AC	2 ms; 6,676 KB
testcase_25	AC	2 ms; 6,676 KB
testcase_26	AC	1 ms; 6,676 KB
testcase_27	AC	1 ms; 6,676 KB
testcase_28	AC	2 ms; 6,676 KB
testcase_29	AC	2 ms; 6,676 KB
testcase_30	AC	2 ms; 6,676 KB
testcase_31	AC	63 ms; 7,032 KB
testcase_32	AC	27 ms; 6,676 KB
testcase_33	AC	23 ms; 6,676 KB
testcase_34	AC	46 ms; 6,676 KB
testcase_35	AC	61 ms; 6,968 KB
testcase_36	AC	52 ms; 6,676 KB
testcase_37	AC	58 ms; 6,776 KB
testcase_38	AC	31 ms; 6,676 KB
testcase_39	AC	70 ms; 7,352 KB
testcase_40	AC	14 ms; 6,676 KB
testcase_41	AC	32 ms; 6,676 KB
testcase_42	AC	46 ms; 6,676 KB
testcase_43	AC	38 ms; 6,676 KB
testcase_44	AC	55 ms; 6,968 KB
testcase_45	AC	36 ms; 6,676 KB
testcase_46	AC	2 ms; 6,676 KB
testcase_47	AC	4 ms; 6,676 KB
testcase_48	AC	2 ms; 6,676 KB
testcase_49	AC	2 ms; 6,676 KB
testcase_50	AC	3 ms; 6,676 KB
testcase_51	AC	3 ms; 6,676 KB
testcase_52	AC	3 ms; 6,676 KB
testcase_53	AC	3 ms; 6,676 KB
testcase_54	AC	3 ms; 6,676 KB
testcase_55	AC	3 ms; 6,676 KB
testcase_56	AC	2 ms; 6,676 KB
testcase_57	AC	3 ms; 6,676 KB
testcase_58	AC	2 ms; 6,676 KB
testcase_59	AC	2 ms; 6,676 KB
testcase_60	AC	2 ms; 6,676 KB
testcase_61	AC	2 ms; 6,676 KB
testcase_62	AC	45 ms; 6,676 KB
testcase_63	AC	2 ms; 6,676 KB
testcase_64	AC	3 ms; 6,676 KB
testcase_65	AC	2 ms; 6,676 KB
testcase_66	AC	2 ms; 6,676 KB
testcase_67	AC	2 ms; 6,676 KB

ソースコード

import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
ImportExpand "neguse/tmpl.nim" <=== "when not declared NEGUSE_TMPL:\n  const NEGUSE_TMPL* = 1\n  {.warning[UnusedImport]: off.}\n  {.hint[XDeclaredButNotUsed]: off.}\n  import algorithm\n  import sequtils\n  import tables\n  import macros\n  import math\n  import sets\n  import strutils\n  import strformat\n  import sugar\n  import heapqueue\n  import streams\n  import deques\n  import bitops\n  import std/lenientops\n  import options\n  # ACL\n  #[ import atcoder/header ]#\n  when not declared ATCODER_HEADER_HPP:\n    const ATCODER_HEADER_HPP* = 1\n    {.hints:off checks:off assertions:on optimization:speed.}\n    {. warning[UnusedImport]:off .}\n    import std/algorithm as algorithm_lib\n    import std/sequtils as sequils_lib\n    import std/tables as tables_lib\n    import std/macros as macros_lib\n    import std/math as math_lib\n    import std/sets as sets_lib\n    import std/strutils as strutils_lib\n    import std/streams as streams_lib\n    import std/strformat as strformat_lib\n  \n    proc scanf*(formatstr: cstring){.header: \"<stdio.h>\", varargs.}\n    proc getchar*(): char {.header: \"<stdio.h>\", varargs.}\n    proc nextInt*(base:int = 0): int =\n      scanf(\"%lld\",addr result)\n      result -= base\n    proc nextFloat*(): float = scanf(\"%lf\",addr result)\n    proc nextString*(): string =\n      var get = false;result = \"\"\n      while true:\n        var c = getchar()\n        if int(c) > int(' '): get = true;result.add(c)\n        elif get: break\n    template `max=`*(x,y:typed):void = x = max(x,y)\n    template `min=`*(x,y:typed):void = x = min(x,y)\n    template inf*(T): untyped = \n      when T is SomeFloat: T(Inf)\n      elif T is SomeInteger: T.high div 2\n      else: assert(false)\n  \n    discard\n  #[ import atcoder/extra/other/inf ]#\n  when not declared ATCODER_INF_HPP:\n    const ATCODER_INF_HPP* = 1\n    import sequtils\n    template inf*(T: typedesc): untyped =\n      when T is SomeFloat: T(Inf)\n      elif T is SomeInteger: T.high div 2\n      else:\n        static: assert(false)\n    template infRepr*[T](x: T): string =\n      when T is seq or T is array:\n        \"@[\" & x.mapIt(it.infRepr).join(\", \") & \"]\"\n      elif x is SomeInteger or x is SomeFloat:\n        when x is SomeUnsignedInt:\n          if x >= T.inf: \"inf\"\n          else: $x\n        else:\n          if x >= T.inf: \"inf\"\n          elif x <= -T.inf: \"-inf\"\n          else: $x\n      else:\n        $x\n    proc isInf*[T](x: T): bool = x >= T.inf\n    proc `∞`*(T: typedesc): T = T.inf\n    proc `*!`*[T: SomeInteger](a, b: T): T =\n      if a == T(0) or b == T(0): return T(0)\n      var sgn = T(1)\n      if a < T(0): sgn = -sgn\n      if b < T(0): sgn = -sgn\n      let a = abs(a)\n      let b = abs(b)\n      if b > T.inf div a: result = T.inf\n      else: result = min(T.inf, a * b)\n      result *= sgn\n    proc `+!`*[T: SomeInteger](a, b: T): T =\n      result = a + b\n      result = min(T.inf, result)\n      result = max(-T.inf, result)\n    proc `-!`*[T: SomeInteger](a, b: T): T =\n      result = a - b\n      result = min(T.inf, result)\n      result = max(-T.inf, result)\n    discard\n\n  # const INF = int.inf\n  const mod998 = 998244353\n  const mod107 = 1000000007\n  const mod109 = 1000000009\n\n  # 演算子\n  proc `%`(x: int, y: int): int = (((x mod y)+y) mod y)\n  proc `//`(x: int, y: int): int = (((x) - (x%y)) div (y))\n  proc `%=`(x: var int, y: int): void = x = x%y\n  proc `//=`(x: var int, y: int): void = x = x//y\n  proc `**`(x: int, y: int): int = x^y\n  proc `**=`(x: var int, y: int): void = x = x^y\n  proc `^`(x: int, y: int): int = x xor y\n  proc `|`(x: int, y: int): int = x or y\n  proc `&`(x: int, y: int): int = x and y\n  proc `>>`(x: int, y: int): int = x shr y\n  proc `<<`(x: int, y: int): int = x shl y\n  proc `~`(x: int): int = not x\n  proc `^=`(x: var int, y: int): void = x = x ^ y\n  proc `&=`(x: var int, y: int): void = x = x & y\n  proc `|=`(x: var int, y: int): void = x = x | y\n  proc `>>=`(x: var int, y: int): void = x = x >> y\n  proc `<<=`(x: var int, y: int): void = x = x << y\n  proc `[]`(x: int, n: int): bool = (x and (1 shl n)) != 0\n  proc mul128(a, b, m: int): int {.importcpp: \"(__int128)(#) * (#) % (#)\", nodecl.}\n  proc powmod(a, n, m: int): int =\n    result = 1\n    var\n      a = a\n      n = n\n    while n > 0:\n      if n mod 2 != 0: result = mul128(result, a, m)\n      if n > 1: a = mul128(a, a, m)\n      n = n shr 1\n    return result\n  # 入出力\n  proc print(args: varargs[string, infRepr]) = echo args.join(\" \")\n  let readNext = iterator(getsChar: bool = false): string {.closure.} =\n    while true:\n      var si: string\n      try: si = stdin.readLine\n      except EOFError: yield \"\"\n      for s in si.split:\n        if getsChar:\n          for i in 0..<s.len():\n              yield s[i..i]\n        else:\n          if s.isEmptyOrWhitespace: continue\n          yield s\n  proc chmin[T](a: var T, b: T): bool {.discardable.} =\n    if a > b:\n      a = b\n      result = true\n    else:\n      result = false\n  proc chmax[T](a: var T, b: T): bool {.discardable.} =\n    if a < b:\n      a = b\n      result = true\n    else:\n      result = false\n  iterator range(stop: int): int =\n    for i in 0..<stop: yield i\n  iterator range(start: int, stop: int, step: int = 1): int =\n    var i = start\n    if step > 0:\n      while i < stop:\n        yield i\n        i += step\n    elif step < 0:\n      while i > stop:\n        yield i\n        i += step\n    else:\n      discard\n  iterator permutation[T](a: openArray[T], r: int): seq[T] =\n    let n = a.len\n    var p = toSeq(0..<r) & newSeqWith(n-r, INF)\n    var loc = toSeq(0..<r)\n    yield loc.mapIt(a[it])\n    while nextPermutation(p):\n      for i, v in p:\n        if v != INF:\n          loc[v] = i\n      yield loc.mapIt(a[it])\n  iterator combinations[T](a: openArray[T], r: int): seq[T] =\n    let n = a.len\n    var p = newSeqWith(r, false) & newSeqWith(n-r, true)\n    let indices = toSeq(0..<n)\n    yield indices.filterIt(not p[it]).mapIt(a[it])\n    while nextPermutation(p):\n      yield indices.filterIt(not p[it]).mapIt(a[it])\n  discard\n"

var N = nextInt()
var A = newSeqWith(N, nextInt())

var S = foldl(A, a ^ b, 0)
if S != 0 or (N == 2 and A[0] == A[1]):
  print("No")
  quit()

var d = initTable[int, int]()
for a in A:
  if not d.hasKey(a):
    d[a] = 0
  d[a] += 1

for k, v in d:
  if v >= 2 or k == 0:
    print("Yes")
    quit()

var ans = false
let M = 1<<13

var dp = newSeqWith(M, false)
dp[A[0]] = true
for i in range(1, N):
  var nxt_dp = newSeqWith(M, false)
  for j in range(M):
    nxt_dp[j] = nxt_dp[j] or dp[j]
    nxt_dp[j xor A[i]] = nxt_dp[j xor A[i]] or dp[j]
  if i == N-1 and not dp[0] and nxt_dp[0]:
    print("No")
    quit()
  dp = nxt_dp

if dp[0]:
  print("Yes")
else:
  print("No")