Submission #14143

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
14143	2015-05-02T08:26:08 Z	gs13105	Be Two Bees (OJUZ10_b2b)	C++	67 / 100	803 ms	3036 KB

b2b

#include <stdio.h>
#include <algorithm>

int h[100000];
int t[100000];
double f[100000];
int arr[100000];
const double EPS=1e-8;

inline bool cmp(const int& a, const int& b)
{
	return f[a]>f[b];
}

int main()
{
	int r1, r2, n, b, i, j;
	double m=0, s=0, g=500000000000000.0, x;
	scanf("%d", &n);
	for(i=0;i<n;i++)
		scanf("%d", &h[i]);
	for(i=0;i<n;i++)
		scanf("%d", &t[i]);
	for(i=0;i<n;i++)
		m+=h[i];
	if(n<=1000)
	{
		double mn=500000000000000.0, c;
		for(i=0;i<n;i++)
		{
			for(j=i+1;j<n;j++)
			{
				c=(m-h[i]-h[j])/(1/t[i]+1/t[j]);
				if(c<mn)
				{
					mn=c;
					r1=i;
					r2=j;
				}
			}
		}
		printf("%d %d", r1+1, r2+1);
		return 0;
	}


	for(b=0;b<40&&s+EPS<g;b++)
	{
		x=(s+g)/2;
		for(i=0;i<n;i++)
		{
			arr[i]=i;
			f[i]=x/t[i]+h[i];
		}
		std::sort(arr, arr+n,cmp);
		if(f[arr[0]]+f[arr[1]]>=m)
		{
			r1=std::min(arr[0], arr[1]);
			r2=std::max(arr[0], arr[1]);
			g=x;
		}
		else
			s=x;
	}
	printf("%d %d", r1+1, r2+1);
	return 0;
}

Subtask #1

0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	3036 KB	Output isn't correct
2	Incorrect	0 ms	3036 KB	Output isn't correct
3	Incorrect	0 ms	3036 KB	Output isn't correct
4	Incorrect	0 ms	3036 KB	Output isn't correct
5	Incorrect	0 ms	3036 KB	Output isn't correct
6	Incorrect	0 ms	3036 KB	Output isn't correct
7	Incorrect	0 ms	3036 KB	Output isn't correct

Subtask #2

0.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	3036 KB	Output isn't correct
2	Incorrect	5 ms	3036 KB	Output isn't correct
3	Incorrect	5 ms	3036 KB	Output isn't correct
4	Incorrect	0 ms	3036 KB	Output isn't correct
5	Incorrect	5 ms	3036 KB	Output isn't correct
6	Incorrect	0 ms	3036 KB	Output isn't correct
7	Incorrect	1 ms	3036 KB	Output isn't correct
8	Incorrect	5 ms	3036 KB	Output isn't correct
9	Incorrect	5 ms	3036 KB	Output isn't correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	612 ms	3036 KB	Output is correct
2	Correct	529 ms	3036 KB	Output is correct
3	Correct	777 ms	3036 KB	Output is correct
4	Correct	244 ms	3036 KB	Output is correct
5	Correct	785 ms	3036 KB	Output is correct
6	Correct	801 ms	3036 KB	Output is correct
7	Correct	281 ms	3036 KB	Output is correct
8	Correct	226 ms	3036 KB	Output is correct
9	Correct	748 ms	3036 KB	Output is correct
10	Correct	434 ms	3036 KB	Output is correct
11	Correct	340 ms	3036 KB	Output is correct
12	Correct	785 ms	3036 KB	Output is correct

Subtask #4

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	803 ms	3036 KB	Output is correct
2	Correct	531 ms	3036 KB	Output is correct
3	Correct	787 ms	3036 KB	Output is correct
4	Correct	425 ms	3036 KB	Output is correct
5	Correct	793 ms	3036 KB	Output is correct
6	Correct	791 ms	3036 KB	Output is correct
7	Correct	784 ms	3036 KB	Output is correct
8	Correct	783 ms	3036 KB	Output is correct
9	Correct	796 ms	3036 KB	Output is correct
10	Correct	783 ms	3036 KB	Output is correct
11	Correct	107 ms	3036 KB	Output is correct
12	Correct	547 ms	3036 KB	Output is correct
13	Correct	524 ms	3036 KB	Output is correct
14	Correct	796 ms	3036 KB	Output is correct
15	Correct	782 ms	3036 KB	Output is correct
16	Correct	520 ms	3036 KB	Output is correct
17	Correct	788 ms	3036 KB	Output is correct