제출 #14017

#제출 시각아이디문제언어결과실행 시간메모리
14017pjsdreamBe Two Bees (OJUZ10_b2b)C++14
100 / 100
285 ms2644 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...