oj.uz

Submission #14016

# Submission time Handle Problem Language Result Execution time Memory
14016 2015-04-25T01:04:46 Z pjsdream Be Two Bees (OJUZ10_b2b) C++14
0 / 100
 1000 ms 2644 KB 
#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];
	while (h-l >= 1e-8) {
		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
0.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 Execution timed out 1000 ms 2640 KB Program timed out

Subtask #2
0.0 / 22.0

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

Subtask #3
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 2640 KB Program timed out
2 Execution timed out 1000 ms 2640 KB Program timed out
3 Execution timed out 1000 ms 2640 KB Program timed out
4 Execution timed out 1000 ms 2640 KB Program timed out
5 Execution timed out 1000 ms 2640 KB Program timed out
6 Execution timed out 1000 ms 2640 KB Program timed out
7 Execution timed out 1000 ms 2640 KB Program timed out
8 Execution timed out 1000 ms 2640 KB Program timed out
9 Correct 172 ms 2644 KB Output is correct
10 Correct 208 ms 2644 KB Output is correct
11 Execution timed out 1000 ms 2640 KB Program timed out
12 Execution timed out 1000 ms 2640 KB Program timed out

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 2640 KB Program timed out
2 Execution timed out 1000 ms 2640 KB Program timed out
3 Execution timed out 1000 ms 2640 KB Program timed out
4 Execution timed out 1000 ms 2640 KB Program timed out
5 Execution timed out 1000 ms 2640 KB Program timed out
6 Execution timed out 1000 ms 2640 KB Program timed out
7 Execution timed out 1000 ms 2640 KB Program timed out
8 Execution timed out 1000 ms 2640 KB Program timed out
9 Execution timed out 1000 ms 2640 KB Program timed out
10 Execution timed out 1000 ms 2640 KB Program timed out
11 Correct 152 ms 2644 KB Output is correct
12 Execution timed out 1000 ms 2640 KB Program timed out
13 Execution timed out 1000 ms 2640 KB Program timed out
14 Execution timed out 1000 ms 2640 KB Program timed out
15 Execution timed out 1000 ms 2640 KB Program timed out
16 Execution timed out 1000 ms 2640 KB Program timed out
17 Execution timed out 1000 ms 2640 KB Program timed out