代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=100005;
int t,n,m,k[MAXN],a[MAXN],stuage[2*MAXN],belong[2*MAXN],newid[MAXN];
struct group{
	int id,sum,left,right;
	group(){id=sum=left=right=0;}
}g[MAXN];
bool cmp(group x,group y)
{
	return x.sum*k[y.id]>y.sum*k[x.id];
}
bool cmp2(int x,int y)
{
	return x>y;
}
inline int mylow(int l,int r,int nownum,int nowsum)
{
	if(l==r)
		return l;
	int mid=(l+r)>>1;
	if(g[mid].sum*nownum>nowsum*k[g[mid].id])//mid平均值较大
	//g[mid].sum/k[g[mid].id>=nowsum/nownum
		return mylow(mid+1,r,nownum,nowsum);
	else return mylow(l,mid,nownum,nowsum);
}
int myup(int l,int r,int nownum,int nowsum)
{
	if(l==r)
		return l;
	int mid=(l+r)>>1;
	if(g[mid].sum*nownum<=nowsum*k[g[mid].id])//mid平均值较xiao
		return myup(l,mid,nownum,nowsum);
	else return myup(mid+1,r,nownum,nowsum);
}
signed main()
{
	cin>>t;
	while(t--)
	{
		bool flag=1;
		int cnt=0;
		memset(k,0,sizeof(k));
		memset(a,0,sizeof(a));
		memset(stuage,0,sizeof(stuage));
		memset(belong,0,sizeof(belong));
		memset(newid,0,sizeof(newid));
		memset(g,0,sizeof(g));
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=m;i++)
		{
			g[i].id=i;
			cin>>k[i];
			int x;
			for(int j=1;j<=k[i];j++) scanf("%lld",&x),stuage[++cnt]=x,belong[cnt]=i,g[i].sum+=x;
		}
		sort(g+1,g+m+1,cmp);
		sort(a+1,a+n+1,cmp2);
		g[0].left=0;
		for(int i=1;i<=m;i++)
		{
			newid[g[i].id]=i;
			if(g[i].sum>a[i]*k[g[i].id]) flag=0;
			if(g[i].sum>a[i+1]*k[g[i].id]) g[i].left=i;
			else g[i].left=g[i-1].left;
		}
		if(flag)//若初始合法 
		{ 
			for(int i=1;i<=cnt;i++)
			{
				int gid=newid[belong[i]];
				int temp=g[gid].sum-stuage[i];
				int newnum=k[g[gid].id]-1;
				if(temp*k[g[gid].id]>g[gid].sum*newnum)//变大 
				{
					int j=mylow(1,gid,newnum,temp);
					if(g[gid-1].left>=j||a[j]*newnum<temp) printf("0");
					else
					{
						/*if(g[gid-1].left>=j) printf("0");
						else*/ printf("1");
					}
				}
				else printf("1");
			}
		}
		else
		{
			for(int i=m;i>=1;i--)
			{
				if(g[i].sum<a[i-1]*k[g[i].id]) g[i].right=i;
				else g[i].right=g[i+1].right;
			}
			for(int i=1;i<=cnt;i++)
			{
				int gid=newid[belong[i]];
				int temp=g[gid].sum-stuage[i];
				int newnum=k[g[gid].id]-1;
				if(temp*k[g[gid].id]<g[gid].sum*newnum)
				{
					int j=myup(gid,m,newnum,temp);
					//printf("\n*%d* *%d*\n",gid,j);
					if(g[gid+1].right>j&&a[j]*newnum>=temp) printf("1");
					else
					{
						/*if(g[gid+1].right>=j) printf("1");
						else*/ printf("0");
					}
				}
				else printf("0");
			}
		}
		cout<<endl;
	}
	return 0;
}

思路如下：

思路