关于百度之星 T3

#include<bits/stdc++.h>
using namespace std;
/*
当去掉 k 限制的时候：
0,1：gcd=1，看 MEX。分最大 MEX,MEX-1 讨论。
0：MEX=1，看 gcd。分最大奇 gcd 和最大偶 gcd 讨论。
1：MEX=0，gcd=1。答案为 1。
什么都不：MEX=0，看 gcd。直接最大 gcd。
*/
struct FSI{
	template<typename T>
	FSI& operator >> (T &res){
		res=0;T f=1;char ch=getchar();
		while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
		while (isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
		res*=f;
		return *this;
	}
}scan;
const int N=4e5+10,M=1e6+15,m=1e6+5;
int n,i,j,a[M],c[M],cnt,k,t,mex[M],d[M][2],ans;
int r0,r1;
int main()
{
	scan>>n;
	for (i=1;i<=n;i++) scan>>a[i],c[a[i]]++;
	for (i=1;i<=n;i++)
	{
		if (a[i]==0) r0++;
		if (a[i]==1) r1++;
	}
	for (i=1;i<=m;i++)
	{
		cnt=0;
		for (j=i;j<=m;j+=i) cnt+=c[j];
		if (cnt) d[cnt][i&1]=max(d[cnt][i&1],i);
	}
	for (i=m-1;i>=1;i--) 
	{
		d[i][0]=max(d[i][0],d[i+1][0]);
		d[i][1]=max(d[i][1],d[i+1][1]);
	}
	sort(a+1,a+n+1);
	k=unique(a+1,a+n+1)-a-1;
	for (i=1;i<=k;i++)
	{
		if (a[i]==t) t++;
		mex[i]=t;
	}
	for (i=k+1;i<=n;i++) mex[i]=mex[k];
	for (i=1;i<=n;i++)
	{
		ans=1;
		if (d[i][0]!=1) ans=max(d[i][0],ans);
		if (d[i][1]!=1) ans=max(d[i][1],ans);
		if (r0&&i>1&&d[max(1,i-r0)][0]!=1) ans=max(ans,(d[max(1,i-r0)][0]^1));
		if (r0&&i>1&&d[max(1,i-r0)][1]!=1) ans=max(ans,(d[max(1,i-r0)][1]^1));
		if (r0&&r1&&i>=2&&mex[i]>=1) 
		{
			ans=max(ans,(mex[i]^1));
			if (i!=n) ans=max(ans,((mex[i]-1)^1));
		}
		printf("%d ",ans);
	}
	return 0;
}