#960479 (Nim) No.2672 Subset Xor Sum

提出ソース

結果

問題	No.2672 Subset Xor Sum
ユーザー	寝癖
提出日時	2024-03-15 22:23:16
言語	Nim (2.0.2)
結果	TLE
実行時間	-
コード長	6,970 bytes
コンパイル時間	4,390 ms
コンパイル使用メモリ	77,584 KB
実行使用メモリ	7,116 KB
最終ジャッジ日時	2024-09-30 01:47:36
合計ジャッジ時間	19,907 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	5 ms 6,816 KB
testcase_01	AC	4 ms 6,816 KB
testcase_02	AC	10 ms 6,816 KB
testcase_03	AC	9 ms 6,816 KB
testcase_04	AC	8 ms 6,816 KB
testcase_05	AC	10 ms 6,816 KB
testcase_06	AC	10 ms 6,820 KB
testcase_07	AC	9 ms 6,820 KB
testcase_08	AC	9 ms 6,816 KB
testcase_09	AC	9 ms 6,820 KB
testcase_10	AC	10 ms 6,820 KB
testcase_11	AC	10 ms 6,820 KB
testcase_12	AC	9 ms 6,816 KB
testcase_13	AC	10 ms 6,816 KB
testcase_14	AC	10 ms 6,816 KB
testcase_15	AC	9 ms 6,820 KB
testcase_16	AC	10 ms 6,816 KB
testcase_17	AC	10 ms 6,820 KB
testcase_18	AC	9 ms 6,820 KB
testcase_19	AC	9 ms 6,820 KB
testcase_20	AC	10 ms 6,820 KB
testcase_21	AC	9 ms 6,820 KB
testcase_22	AC	10 ms 6,816 KB
testcase_23	AC	10 ms 6,820 KB
testcase_24	AC	9 ms 6,816 KB
testcase_25	AC	9 ms 6,816 KB
testcase_26	AC	1 ms 6,816 KB
testcase_27	AC	1 ms 6,820 KB
testcase_28	AC	10 ms 6,816 KB
testcase_29	AC	10 ms 6,816 KB
testcase_30	AC	9 ms 6,816 KB
testcase_31	AC	61 ms 6,844 KB
testcase_32	AC	26 ms 6,816 KB
testcase_33	AC	22 ms 6,820 KB
testcase_34	AC	45 ms 6,820 KB
testcase_35	AC	60 ms 6,820 KB
testcase_36	AC	52 ms 6,816 KB
testcase_37	AC	59 ms 6,820 KB
testcase_38	AC	30 ms 6,816 KB
testcase_39	AC	64 ms 7,116 KB
testcase_40	AC	13 ms 6,816 KB
testcase_41	AC	31 ms 6,816 KB
testcase_42	AC	46 ms 6,816 KB
testcase_43	AC	37 ms 6,816 KB
testcase_44	AC	54 ms 6,816 KB
testcase_45	AC	35 ms 6,820 KB
testcase_46	AC	2 ms 6,816 KB
testcase_47	TLE	-
testcase_48	AC	2 ms 6,816 KB
testcase_49	AC	2 ms 6,820 KB
testcase_50	AC	2 ms 6,816 KB
testcase_51	TLE	-
testcase_52	AC	3 ms 6,816 KB
testcase_53	AC	3 ms 6,820 KB
testcase_54	TLE	-
testcase_55	TLE	-
testcase_56	AC	2 ms 6,820 KB
testcase_57	AC	1,448 ms 6,816 KB
testcase_58	AC	507 ms 6,816 KB
testcase_59	AC	2 ms 6,820 KB
testcase_60	AC	2 ms 6,820 KB
testcase_61	AC	1 ms 6,816 KB
testcase_62	AC	901 ms 6,816 KB
testcase_63	AC	1,100 ms 6,820 KB
testcase_64	AC	3 ms 6,820 KB
testcase_65	AC	520 ms 6,816 KB
testcase_66	WA	-
testcase_67	AC	2 ms 6,816 KB

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

ソースコード

raw source code

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:
  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:
    print("Yes")
    quit()

let M = 1<<14

# dp[i][j][k] := i個目までみてxor総和をjとできるか? kは1個以上使ったかフラグ
var dp = newSeqWith(M, @[false, false])
dp[0][0] = true


for i in range(N-1):
  var nxt = newSeqWith(M, @[false, false])
  for j in range(M):
    nxt[j][0] = nxt[j][0] or dp[j][0]
    nxt[j][1] = nxt[j][1] or dp[j][1]
    nxt[j^A[i]][1] = nxt[j^A[i]][1] or dp[j][1] or dp[j][0]
  dp = nxt

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

yukicoder

結果

テストケース

ソースコード