Submission #14017

#TimeUsernameProblemLanguageResultExecution timeMemory
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...