Submission #6241236


Source Code Expand

Copy
N,L = gets.split.map &:to_i
S = (0...N).map{ gets.chomp }.sort
prefixes = {}
U = []
V = []
S.each{ |s| 
  n = s.to_i(2)
  m = s.reverse.to_i(2)
#  p n
  t = 1
  s.size.times{ |i|
    t = (t << 1) | m[i]
    prefixes[t] = 1
  }
  V << n
  U << t
}
#p prefixes.size
visited = {}
heads = {}
ns = {}
(0...N).each{ |j|
  s = S[j]
  u = U[j]
  n = V[j]
  (0...s.size).reverse_each{ |i|
    #break if visited[u]
    t = u ^ 1
    if !prefixes[t] && !heads[t]
      heads[t] = 1
      ns[L - i] = (ns[L - i] || 0) + 1
    end
    #visited[u] = 1
    u >>= 1
  }
}
# exit
#p heads, 
#p ns
# exit

def lsb(n)
  return 0 if n == 0
  n & -n
end

g = 0
ns.each{ |k,n|
  next if n % 2 == 0
  g ^= lsb(k)
}
puts g == 0 ? "Bob" : "Alice"

Submission Info

Submission Time
Task E - Prefix-free Game
User Corvvs
Language Ruby (2.3.3)
Score 0
Code Size 774 Byte
Status

Compile Error

./Main.rb:1: warning: `&' interpreted as argument prefix
./Main.rb:25: warning: assigned but unused variable - n
./Main.rb:19: warning: assigned but unused variable - visited

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 0_05.txt
All 0 / 700 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 0_05.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt
Case Name Status Exec Time Memory
0_00.txt 7 ms 1788 KB
0_01.txt 7 ms 1788 KB
0_02.txt 7 ms 1788 KB
0_03.txt 7 ms 1788 KB
0_04.txt 7 ms 1788 KB
0_05.txt 7 ms 1788 KB
1_00.txt 7 ms 1788 KB
1_01.txt 7 ms 1788 KB
1_02.txt 7 ms 1788 KB
1_03.txt 7 ms 1788 KB
1_04.txt 7 ms 1788 KB
1_05.txt 7 ms 1788 KB
1_06.txt
1_07.txt
1_08.txt
1_09.txt
1_10.txt
1_11.txt 36 ms 3192 KB
1_12.txt 98 ms 2808 KB
1_13.txt 100 ms 2808 KB
1_14.txt 73 ms 4216 KB
1_15.txt 66 ms 4216 KB
1_16.txt 66 ms 4216 KB
1_17.txt 66 ms 4216 KB
1_18.txt 68 ms 4216 KB
1_19.txt 67 ms 4216 KB
1_20.txt 65 ms 6136 KB
1_21.txt 67 ms 4216 KB
1_22.txt 70 ms 4216 KB
1_23.txt 67 ms 4216 KB
1_24.txt 72 ms 4216 KB
1_25.txt 71 ms 4216 KB
1_26.txt 66 ms 4216 KB
1_27.txt 64 ms 4216 KB
1_28.txt 68 ms 4216 KB
1_29.txt 67 ms 4216 KB
1_30.txt 71 ms 4216 KB
1_31.txt 69 ms 6264 KB
1_32.txt 66 ms 4216 KB
1_33.txt 68 ms 4216 KB
1_34.txt 66 ms 4216 KB
1_35.txt 69 ms 4216 KB
1_36.txt 68 ms 4344 KB
1_37.txt 69 ms 4216 KB
1_38.txt 68 ms 4216 KB
1_39.txt 66 ms 4216 KB
1_40.txt 67 ms 4216 KB
1_41.txt 67 ms 4216 KB
1_42.txt 67 ms 4216 KB
1_43.txt 66 ms 4216 KB
1_44.txt 72 ms 4216 KB
1_45.txt 67 ms 4216 KB
1_46.txt 67 ms 4216 KB
1_47.txt 66 ms 4216 KB
1_48.txt 66 ms 4216 KB
1_49.txt 67 ms 4216 KB
1_50.txt 67 ms 4216 KB
1_51.txt 66 ms 4216 KB
1_52.txt 66 ms 4216 KB
1_53.txt 69 ms 4216 KB