CE!!!(玄关)
查看原帖
CE!!!(玄关)
716013
tornado01楼主2024/3/20 23:15

为什么代码在CF上AC,但在洛谷上却说 远端 OJ 尚未返回编译信息 是RMJ炸了吗?

#include<bits/stdc++.h>
#define int long long
int n,k,f[1010],tong[1010],tmp[1010];
using namespace std;
map<int,int> mp,sum,vis;
int isprime[1001000];
int prime[1001000],len=0,m=0,cnt=0;
map<int,map<int,int> > ans;
pair<int,int> temp[100100];
int res[100100];
void init()
{
	const int n=1000000;
	isprime[1]=1; 
	for(int i=2;i<=n;i++)
	{ 
		if(!isprime[i]) prime[++len]=i,isprime[i]=i;
		for(int j=1;j<=len&&i*prime[j]<=n;j++)
		{
			isprime[i*prime[j]]=prime[j];
			if(!(i%prime[j])) break;
		}
	}
	return ;
}
bool cmp(pair<int,int> a,pair<int,int> b)
{
	if(a.first!=b.first) return a.first>b.first;
	return a.second<b.second;
}
bool cmp2(pair<int,int> a,pair<int,int> b)
{
	return vis[a.second]>vis[b.second]; 
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	init();
	cin>>n>>k;
	int maxx=0;
	for(int i=1;i<=n;i++) cin>>f[i],mp[f[i]]++,maxx=max(maxx,f[i]);
	for(int i=1;i<=len;i++)
	{
		__int128 nw=prime[i];
		while(nw<=maxx) 
		{
			if(mp[nw]) sum[prime[i]]+=mp[nw],ans[prime[i]][nw]+=mp[nw],vis[nw]=1; 
			nw*=prime[i];
		}
	}
	for(int i=1;i<=n;i++)
	{
		
		if(f[i]<=1e9&&(!vis[f[i]]))
		{
			int temp=f[i];
			bool tf=0;
			for(int j=1;j<=len&&prime[j]*prime[j]<=temp;j++) if(!(temp%prime[j])) {tf=1;break;}
			if(!tf) sum[temp]++,ans[temp][f[i]]++;
		}
		if(f[i]>1e12&&(!vis[f[i]]))
		{
			int temp=sqrt(f[i]);
			if(temp*temp!=f[i]) continue;
			bool tf=0;
			for(int j=1;j<=len&&prime[j]*prime[j]<=temp;j++) if(!(temp%prime[j])) {tf=1;break;}
			if(!tf) sum[temp]++,ans[temp][f[i]]++;
		}
	}
	for(auto i:sum) if(i.second>1) temp[++cnt]={i.second,i.first};
	sort(temp+1,temp+cnt+1,cmp);
	//for(int i=1;i<=cnt;i++) cout<<temp[i].first<<" "<<temp[i].second<<"\n";
	if(k==1) {cout<<0;return 0;}
	int r=n;
	for(int i=1;i<=n;i++)
	{
		int ii=f[i];
		for(int j=1;j<=cnt;j++) while((!(ii%temp[j].second))&&ii) ii/=temp[j].second;
		if(ii!=1) r--;
	}
	if(r<k) {cout<<0;return 0;}
	if(k>=2*cnt)
	{
		for(int i=1;i<=cnt;i++) res[i]=2;
		int rr=0;
		for(int i=1;i<=cnt;i++)
		{
			for(auto j:ans[temp[i].second])
			{
				const int up=j.second,zhi=j.first;
				for(int kk=1;kk<=up;kk++)
				{
					tmp[++rr]=zhi,res[i]--,mp[zhi]--,k--;
					if(!res[i]) break;
				}
				if(!res[i]) break;
			}
		}
		//cout<<"!!!!!!!!!!!\n";
		for(auto i:mp)
		{
			const int up=i.second,zhi=i.first;
			int ii=zhi;
			for(int j=1;j<=cnt;j++)
			{
				bool tf=0;
				while((!(ii%temp[j].second))&&ii) ii/=temp[j].second,tf=1;
			}
			if(ii!=1) continue;
			for(int j=1;j<=up;j++) {if(!k) break;tmp[++rr]=zhi,k--;}
			if(!k) break;
		}
		for(int i=1;i<=rr;i++) cout<<tmp[i]<<" "; 
		return 0;
	}
	if(k%2==0)
	{
		for(int i=1;i<=cnt;i++) res[i]=2;
		const int rr=k/2;
		for(int i=1;i<=rr;i++)
		{
			for(auto j:ans[temp[i].second])
			{
				const int up=j.second,zhi=j.first;
				for(int kk=1;kk<=up;kk++)
				{
					cout<<zhi<<" ",res[i]--,mp[zhi]--,k--;
					if(!res[i]) break;
				}
				if(!res[i]) break;
			}
		}
		return 0;
	}
	if(temp[1].first>=3)
	{
		res[1]=3;
		for(int i=2;i<=cnt;i++) if(!res[i]) res[i]=2;
		const int rr=k/2;
		for(int i=1;i<=rr;i++)
		{
			for(auto j:ans[temp[i].second])
			{
				const int up=j.second,zhi=j.first;
				for(int kk=1;kk<=up;kk++)
				{
					cout<<zhi<<" ",res[i]--,mp[zhi]--,k--;
					if(!res[i]) break;
				}
				if(!res[i]) break;
			}
		}
		return 0;
	} 
	bool tt=0;
	for(int i=1;i<=n;i++)
	{
		int tp=0,ii=f[i],ll=0;vis.clear();
		for(int j=1;j<=cnt;j++)
		{
			bool tf=0;
			while((!(ii%temp[j].second))&&ii) ii/=temp[j].second,tf=1;
			if(tf) vis[temp[j].second]=1,ll++;
		}
		if(ii!=1||ll*2+1>k||ll==1) continue;
		sort(temp+1,temp+cnt+1,cmp2);
		cout<<f[i]<<" ",k--; 
		for(int j=1;j<=cnt;j++) res[j]=2;
		const int rr=k/2;
		for(int j=1;j<=rr;j++)
		{
			for(auto w:ans[temp[j].second])
			{
				const int up=w.second,zhi=w.first;
				for(int kk=1;kk<=up;kk++)
				{
					cout<<zhi<<" ",res[j]--,mp[zhi]--,k--;
					if(!res[j]) break;
				}
				if(!res[j]) break;
			}
		}
		tt=1;break;
	}
	if(!tt) cout<<0;
	return 0; 
}
2024/3/20 23:15
加载中...