fork download
copy 
  1. import sys
  2. from itertools import permutations
  3.  
  4. def blocks_can_block(n, s, cnt0, cnt1, cnt2):
  5.     full_mask = (1 << (s+1)) - 1
  6.     for order in permutations((0,1,2), 3):
  7.         # build the clustered array
  8.         arr = []
  9.         for v in order:
  10.             if v == 0:
  11.                 arr += [0]*cnt0
  12.             elif v == 1:
  13.                 arr += [1]*cnt1
  14.             else:
  15.                 arr += [2]*cnt2
  16.  
  17.         # bitset DP: dp[i] is an int whose bits represent which sums are reachable at index i
  18.         dp = [0]*n
  19.         dp[0] = 1 << arr[0]
  20.  
  21.         # we'll do up to n*(s//min_nonzero+1) iterations, but break early
  22.         # since min_nonzero is 1, that's n*(s+1) worst case
  23.         for _ in range(n*(s+1)):
  24.             new_dp = [0]*n
  25.             for i in range(n):
  26.                 # shift the neighbor‐masks by arr[i] and OR together
  27.                 m = 0
  28.                 if i>0:
  29.                     m |= dp[i-1]
  30.                 if i+1<n:
  31.                     m |= dp[i+1]
  32.                 # move along i by picking up arr[i]
  33.                 new_dp[i] = (m << arr[i]) & full_mask
  34.             if new_dp == dp:
  35.                 break
  36.             dp = new_dp
  37.  
  38.         # if bit s is NOT set at index n-1, Alice cannot reach exactly s
  39.         if not (dp[n-1] >> s) & 1:
  40.             return arr
  41.  
  42.     return None
  43.  
  44. def main():
  45.     input = sys.stdin.readline
  46.     t = int(input())
  47.     out = []
  48.     for _ in range(t):
  49.         n, s = map(int, input().split())
  50.         a = list(map(int, input().split()))
  51.         cnt0, cnt1, cnt2 = a.count(0), a.count(1), a.count(2)
  52.         ans = blocks_can_block(n, s, cnt0, cnt1, cnt2)
  53.         if ans is None:
  54.             out.append("-1")
  55.         else:
  56.             out.append(" ".join(map(str, ans)))
  57.     sys.stdout.write("\n".join(out))
  58.  
  59. if __name__ == "__main__":
  60.     main()
  61.  
Success #stdin #stdout 0.13s 14052KB
comments (?)
stdin
copy 
6
3 2
0 1 2
3 3
0 1 2
3 6
0 1 2
3 4
0 1 2
3 10
0 1 2
5 1000
2 0 1 1 2
stdout
copy 
0 1 2
0 1 2
0 1 2
0 1 2
0 1 2
0 1 1 2 2
https://ideone.com/CZEXId
language:
Python 3 (python  3.12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!