Submission #14365

#TimeUsernameProblemLanguageResultExecution timeMemory
14365FakeableBe Two Bees (OJUZ10_b2b)C++98
0 / 100
1000 ms3428 KiB
#include<cstdio>
#include<algorithm>
#include<utility>
using namespace std;
const int MAX_N = 100100;
pair<double,int> p[MAX_N];
int n,s[MAX_N],t[MAX_N],sum;
void input() {
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%d",&s[i]);
        sum += s[i];
    }
    for(int i=0;i<n;i++) scanf("%d",&t[i]);
    return;
}
bool decision(double x) {
    for(int i=0;i<n;i++) {
        p[i].first = (double)x/t[i]+(double)s[i];
        p[i].second = i+1;
    }
    sort(p,p+n);
    if(p[n-1].first + p[n-2].second >= (double)sum) return true;
    return false;
}
void solve() {
    double lo = 0, hi = 500000000000000.0;
    int ct = 0;
    while(ct < 200) {
        double mid = (lo + hi)/2;
        if(decision(mid)) hi = mid;
        else lo = mid;
        ct ++;
    }
    if(p[n-1].second > p[n-2].second) {
        p[n-1].second += p[n-2].second;
        p[n-2].second = p[n-1].second - p[n-2].second;
        p[n-1].second -= p[n-2].second;
    }
    printf("%d %d\n",p[n-1].second, p[n-2].second);
    return;
}
int main() {
    input();
    solve();
    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...