This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |