Submission #14017

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
14017	2015-04-25T01:09:26 Z	pjsdream	Be Two Bees (OJUZ10_b2b)	C++14	100 / 100	285 ms	2644 KB

b2b

#pragma warning(disable:4996)

#include <stdio.h>
#include <algorithm>
using namespace std;

int n;
double a[100000];
double b[100000];

int sign(double x) { return x > 0 ? 1 : x < 0 ? -1 : 0; }
int compare(double a1, double b1, double a2, double b2, double p)
{
	// a1 + b1 * p - a2 - b2 * p = (a1-a2) + p * (b1-b2)

	double da = a1 - a2;
	double db = b1 - b2;

	// da + p * db

	if (db == 0) return sign(da);
	return sign(da + p*db);
}

int main ()
{
	long long S=0;

	scanf("%d", &n);
	for (int i=0; i<n; i++) {
		int x;
		scanf("%d", &x);
		a[i] = x;

		S += x;
	}
	for (int i=0; i<n; i++) {
		int x;
		scanf("%d", &x);
		b[i] = 1. / x;
	}

	double l=0, h=1e15;
	double res;
	int ans[2];
	for (int it = 0; it <= 100; it++) {
		double p = (l+h)/2;

		int m1 = -1;
		int m2 = -1;
		for (int i=0; i<n; i++) {
			if (m1 == -1 || compare(a[m1], b[m1], a[i], b[i], p) <= 0)
				m1 = i;
		}
		for (int i=0; i<n; i++) if (i != m1) {
			if (m2 == -1 || compare(a[m2], b[m2], a[i], b[i], p) <= 0)
				m2 = i;
		}

		if (a[m1] + a[m2] + p * (b[m1] + b[m2]) - S >= 0) {
			ans[0] = m1;
			ans[1] = m2;
			h = p;
		}
		else l = p;
	}

	if (ans[0] > ans[1]) swap(ans[0], ans[1]);

	printf("%d %d\n", ans[0]+1, ans[1]+1);

	return 0;
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2644 KB	Output is correct
2	Correct	0 ms	2644 KB	Output is correct
3	Correct	0 ms	2644 KB	Output is correct
4	Correct	0 ms	2644 KB	Output is correct
5	Correct	0 ms	2644 KB	Output is correct
6	Correct	0 ms	2644 KB	Output is correct
7	Correct	0 ms	2644 KB	Output is correct

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2644 KB	Output is correct
2	Correct	3 ms	2644 KB	Output is correct
3	Correct	3 ms	2644 KB	Output is correct
4	Correct	3 ms	2644 KB	Output is correct
5	Correct	0 ms	2644 KB	Output is correct
6	Correct	3 ms	2644 KB	Output is correct
7	Correct	0 ms	2644 KB	Output is correct
8	Correct	0 ms	2644 KB	Output is correct
9	Correct	0 ms	2644 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	91 ms	2644 KB	Output is correct
2	Correct	262 ms	2644 KB	Output is correct
3	Correct	275 ms	2644 KB	Output is correct
4	Correct	281 ms	2644 KB	Output is correct
5	Correct	161 ms	2644 KB	Output is correct
6	Correct	133 ms	2644 KB	Output is correct
7	Correct	260 ms	2644 KB	Output is correct
8	Correct	221 ms	2644 KB	Output is correct
9	Correct	270 ms	2644 KB	Output is correct
10	Correct	246 ms	2644 KB	Output is correct
11	Correct	192 ms	2644 KB	Output is correct
12	Correct	269 ms	2644 KB	Output is correct

Subtask #4

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	273 ms	2644 KB	Output is correct
2	Correct	285 ms	2644 KB	Output is correct
3	Correct	267 ms	2644 KB	Output is correct
4	Correct	279 ms	2644 KB	Output is correct
5	Correct	279 ms	2644 KB	Output is correct
6	Correct	93 ms	2644 KB	Output is correct
7	Correct	269 ms	2644 KB	Output is correct
8	Correct	284 ms	2644 KB	Output is correct
9	Correct	193 ms	2644 KB	Output is correct
10	Correct	273 ms	2644 KB	Output is correct
11	Correct	268 ms	2644 KB	Output is correct
12	Correct	275 ms	2644 KB	Output is correct
13	Correct	270 ms	2644 KB	Output is correct
14	Correct	196 ms	2644 KB	Output is correct
15	Correct	281 ms	2644 KB	Output is correct
16	Correct	270 ms	2644 KB	Output is correct
17	Correct	163 ms	2644 KB	Output is correct