链接：https://ac.nowcoder.com/acm/contest/4784/H

有一个容量为2^{30}230的背包，和m件物品，第i件物品的体积为c_ici​，你需要从中选出若干件，使得选出的物品的体积恰好等于背包容量。这些物品有一个奇怪的特性，那就是c_i = 2^{k_i}ci​=2ki​，其中0 \le k_i < 300≤ki​<30，即所有c_ici​都是2的幂。

输入描述:

第一行，是一个正整数T(1 \le T \le 100000)T(1≤T≤100000)，表示接下来要输入T组测试数据
接下来有T测试数据的输入，对于每组测试数据，输入格式如下：
第一行，一个整数m(1 \le m \le 100000, \sum m \le 10^5)m(1≤m≤100000,∑m≤105)
第二行，用空格隔开的m个非负整数，第i个数字是k_i (0 \le k_i < 30)ki​(0≤ki​<30)

输出描述:

依次输出T行，按照输入数据的顺序依次给出每组测试数据的答案，对于一组测试数据：
如果存在一种符合条件的方案，则输出一个长度为m的01串，从前往后的第i位如果是1表示原序列中第i个物品被选中装进背包，为0则表示这个物品不被选中。
如果不存在符合条件的方案，请输出impossible

示例1

输入

复制

2
4
29 1 28 28
7
0 0 1 2 3 4 15

输出

复制

1011
impossible

代码：

#include <bits/stdc++.h>
using namespace std;
long long n,t,s1,s2;
long long a[2000001],ans[2000001];
map<long long,long long>m,p[30];
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		m.clear();
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			ans[i]=0;
			m[a[i]]++;
			p[a[i]][m[a[i]]]=i;
		}
		long long s=2,j=0;
		for(int i=29;i>=0;i--)
		{
			if(m[i]>=s)
			{
				for(int k=1;k<=min(m[i],s);k++)
				{
					j++;
					ans[p[i][k]]=1;
				}
				s=0;
				break;
			}
			else
			{
				for(int k=1;k<=m[i];k++)
				{
					j++;
					ans[p[i][k]]=1;
				}
				s-=m[i];
				s*=2;
			}
		}
		if(s==0)
		{
			for(int i=1;i<=n;i++)
			{
				cout<<ans[i];
			}
			cout<<endl;
		}
		else
		{
			cout<<"impossible"<<endl;
		}
		
	}
	
}