C(clang11) 解法, 执行用时: 20ms, 内存消耗: 1460K, 提交时间: 2021-02-03 20:00:21

#include<stdio.h>

#define mod 1000000007

int ans[100005],a[100005];
int main() {
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,i;
        scanf("%d",&n);
        for(i=1;i<=n;i++) 
			scanf("%d",&a[i]);
        int now=1;
        for(i=29;i>=0;i--)
        {
            now*=2;
            for(int j=1;j<=n;j++)
                if(a[j]==i&&now){ --now;ans[j]=1;}
        }
        if(now) puts("impossible");
        else{
            for(int i=1;i<=n;i++)
                printf("%d",ans[i]);
            puts("");
        }
        for(i=1;i<=n;i++) ans[i]=0;
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 44ms, 内存消耗: 1328K, 提交时间: 2020-09-23 21:01:14

#include<bits/stdc++.h>
using namespace std;
const int nx=1e5+5;
int a[nx],f[nx],t,m,k;
bool vis[nx];
bool cmp(int x,int y){
	return a[x]>a[y];
}
int main(){
	scanf("%d",&t);
	while(t--){
		memset(vis,0,sizeof vis);
		scanf("%d",&m);
		for(int i=0;i<m;++i)
			scanf("%d",&k),a[i]=1<<k,f[i]=i;
		sort(f,f+m,cmp);
		int now=1<<30;
		for(int i=0;i<m;++i){
			if(now>=a[f[i]])now-=a[f[i]],vis[f[i]]=1;
			if(!now)break;
		}
		if(now)puts("impossible");
		else{
			for(int i=0;i<m;++i)
				printf("%d",vis[i]);
			putchar('\n');
		}
	}
}

C++(clang++11) 解法, 执行用时: 37ms, 内存消耗: 1784K, 提交时间: 2021-05-08 03:24:53

#include<bits/stdc++.h>
using namespace std;

int i,j,n,t,k,a[100500];
vector<int> v[35];

int main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(i=1;i<=30;i++){v[i].clear();}
		for(i=1;i<=n;i++){cin>>k;v[k].push_back(i);a[i]=0;}
		for(i=29,k=2;i>=0;i--){
			for(auto j:v[i]){if(k){k--;a[j]=1;}}k*=2;
		}
		if(k){puts("impossible");}
		else{
			for(i=1;i<=n;i++){printf("%d",a[i]);}puts("");
		}
	}
}