题号:NC204441
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld
题目描述
有一个容量为

的背包,和m件物品,第i件物品的体积为

,你需要从中选出若干件,使得选出的物品的体积恰好等于背包容量。这些物品有一个奇怪的特性,那就是

,其中

,即所有

都是2的幂。
输入描述:
第一行,是一个正整数
,表示接下来要输入T组测试数据
接下来有T测试数据的输入,对于每组测试数据,输入格式如下:
第一行,一个整数)
第二行,用空格隔开的m个非负整数,第i个数字是)
输出描述:
依次输出T行,按照输入数据的顺序依次给出每组测试数据的答案,对于一组测试数据:
如果存在一种符合条件的方案,则输出一个长度为m的01串,从前往后的第i位如果是1表示原序列中第i个物品被选中装进背包,为0则表示这个物品不被选中。
如果不存在符合条件的方案,请输出impossible
示例1
输入
复制
2
4
29 1 28 28
7
0 0 1 2 3 4 15