C++14(g++5.4) 解法, 执行用时: 145ms, 内存消耗: 3180K, 提交时间: 2020-04-10 10:15:41

#include <stdio.h>
#include <algorithm>
#define ll long long
using namespace std;
struct node
{
	int id,v;
	bool f;
}a[100010],b[100010];
int main()
{
	int n;
	scanf("%d",&n);	
	for(int i=1;i<=n;i++)scanf("%d",&a[i].v),a[i].id=i;
	for(int i=1;i<=n;i++)scanf("%d",&b[i].v),b[i].id=i;
	sort(a+1,a+1+n,[](node p,node q){return p.v>q.v;});
	sort(b+1,b+1+n,[](node p,node q){return p.v>q.v;});
	node *A=a,*B=b;
	ll left=0,right=0,i=1,j=1,num=0;
	while((A[i].v>1||B[j].v>1)&&i<=n&&j<=n)
	{
		if(left>right)
		{
			swap(left,right);
			swap(A,B);
			swap(i,j);
		}
		if(A[i].v<=1)break;
		A[i].f=1;
		left+=A[i].v;
		i++;
		num++;
	}
	sort(a+1,a+1+n,[](node p,node q){return p.id<q.id;});
	sort(b+1,b+1+n,[](node p,node q){return p.id<q.id;});
	printf("%lld\n",min(left,right)-num);
	for(int i=1;i<=n;i++)printf("%d ",a[i].f);
	putchar('\n');
	for(int i=1;i<=n;i++)printf("%d ",b[i].f);
	
} 

C++11(clang++ 3.9) 解法, 执行用时: 101ms, 内存消耗: 3040K, 提交时间: 2019-04-05 22:01:27

#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define F2(i,a,b) for(int i=a;i<(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define MN 6000005
#define ll long long
int n,m,q,k;
int a[MN],b[MN],ap[MN],bp[MN];
int h[MN];
ll ans=0,ii=1,jj=1;
int main(){
	scanf("%d",&n);
	F(i,1,n)scanf("%d",a+i),ap[i]=i;
	F(i,1,n)scanf("%d",b+i),bp[i]=i;
	sort(ap+1,ap+n+1,[](int i,int j){return a[i]>a[j];});
	sort(bp+1,bp+n+1,[](int i,int j){return b[i]>b[j];});
	int i=1,j=1;
	ll s1=0,s2=0;
	while(i<=n||j<=n){
		int s;
		if(i<=n&&j<=n)s=s2<s1;
		else s=j<=n;
		if(s)s2+=b[bp[j++]];
		else s1+=a[ap[i++]];
		if(ans<min(s1,s2)-i-j+2)
			ans=min(s1,s2)-i-j+2,ii=i,jj=j;
	}printf("%lld\n",ans);
	F2(i,1,ii)h[ap[i]]=1;
	F(i,1,n)printf("%d ",h[i]);puts("");
	F(i,1,n)h[i]=0;
	F2(i,1,jj)h[bp[i]]=1;
	F(i,1,n)printf("%d ",h[i]);
	return 0;
}