Submission #14144

#TimeUsernameProblemLanguageResultExecution timeMemory
14144ggohBe Two Bees (OJUZ10_b2b)C++98
61 / 100
1000 ms4988 KiB
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
int a,b,i,j,k,m,X,Y,p=1,q=2,T1[100002],T2[100002];
long double H,x[100001],y[100001];
long double com(int ii,int jj)
{
	return (H-x[ii]-x[jj])/(y[ii]+y[jj])*y[ii]*y[jj];
}
main()
{
	scanf("%d",&a);
	for(i=1;i<=a;i++)
	{
		scanf("%Lf",&x[i]);
		H+=x[i];
	}
	for(j=1;j<=a;j++)
	{
		scanf("%Lf",&y[j]);
		if(m<y[j])m=y[j];
	}
	if(a<=1000)
	{
		for(i=1;i<=a;i++)
		{
			for(j=i+1;j<=a;j++)
			{
				if(com(i,j)<com(p,q))p=i,q=j;
			}
		}
		printf("%d %d",p,q);
	}
	else
	{
		for(i=1;i<=a;i++)
		{
			if(T1[(int)y[i]]==0)
			{
				T1[(int)y[i]]=i;
			}
			else
			{
				if(x[i]>=x[T1[(int)y[i]]])
				{
					T2[(int)y[i]]=T1[(int)y[i]];
					T1[(int)y[i]]=i;
				}
				else if(T2[(int)y[i]]==0)T2[(int)y[i]]=i;
				else if(x[i]>=x[T2[(int)y[i]]])
				{
					T2[(int)y[i]]=i;
				}
			}
		}
		for(i=1;i<=m;i++)
		{
			if(T1[i]!=0&&T2[i]!=0&&com(T1[i],T2[i])<com(p,q))p=T1[i],q=T2[i];
			for(j=i+1;j<=m;j++)
			{
				if(T1[i]!=0&&T1[j]!=0&&com(T1[i],T1[j])<com(p,q))p=T1[i],q=T1[j];
			}
		}
		if(p>q)printf("%d %d",q,p);
		else printf("%d %d",p,q);
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...