Submission #14141

#TimeUsernameProblemLanguageResultExecution timeMemory
14141ggohBe Two Bees (OJUZ10_b2b)C++98
33 / 100
1000 ms5772 KiB
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
long long 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(k=1;k<=m;k++)
		{
			if(T1[k])i=T1[k];
			{
				for(j=1;j<=m;j++)
				{
					if(T1[j]&&T1[j]!=i)
					{
						if(com(i,T1[j])<com(p,q))p=i,q=T1[j];
					}
					else if(T2[j])
					{
						if(com(i,T2[j])<com(p,q))p=i,q=T2[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...