#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;
}
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
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 |
