oj.uz

Submission #14368

# Submission time Handle Problem Language Result Execution time Memory
14368 2015-05-13T00:05:31 Z Fakeable Be Two Bees (OJUZ10_b2b) C++
100 / 100
 139 ms 3428 KB 
#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];
long long sum;
void input() {
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%d",&s[i]);
        sum += (long long)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;
    }
    for(int i=0;i<n;i++) {
        if(p[i].first > p[n-1].first) {
            swap(p[i], p[n-1]);
        }
    }
    for(int i=0;i<n-1;i++) {
        if(p[i].first > p[n-2].first) {
            swap(p[i], p[n-2]);
        }
    }
    if(p[n-1].first + p[n-2].first >= (double)sum) return true;
    return false;
}
void solve() {
    double lo = 0, hi = 500000000000000.0;
    int ct = 0;
    while(ct < 80) {
        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;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3428 KB Output is correct
2 Correct 0 ms 3428 KB Output is correct
3 Correct 0 ms 3428 KB Output is correct
4 Correct 0 ms 3428 KB Output is correct
5 Correct 0 ms 3428 KB Output is correct
6 Correct 1 ms 3428 KB Output is correct
7 Correct 0 ms 3428 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3428 KB Output is correct
2 Correct 0 ms 3428 KB Output is correct
3 Correct 1 ms 3428 KB Output is correct
4 Correct 1 ms 3428 KB Output is correct
5 Correct 2 ms 3428 KB Output is correct
6 Correct 0 ms 3428 KB Output is correct
7 Correct 0 ms 3428 KB Output is correct
8 Correct 0 ms 3428 KB Output is correct
9 Correct 0 ms 3428 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3428 KB Output is correct
2 Correct 136 ms 3428 KB Output is correct
3 Correct 122 ms 3428 KB Output is correct
4 Correct 132 ms 3428 KB Output is correct
5 Correct 58 ms 3428 KB Output is correct
6 Correct 127 ms 3428 KB Output is correct
7 Correct 129 ms 3428 KB Output is correct
8 Correct 81 ms 3428 KB Output is correct
9 Correct 94 ms 3428 KB Output is correct
10 Correct 123 ms 3428 KB Output is correct
11 Correct 45 ms 3428 KB Output is correct
12 Correct 131 ms 3428 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 3428 KB Output is correct
2 Correct 81 ms 3428 KB Output is correct
3 Correct 92 ms 3428 KB Output is correct
4 Correct 123 ms 3428 KB Output is correct
5 Correct 139 ms 3428 KB Output is correct
6 Correct 134 ms 3428 KB Output is correct
7 Correct 131 ms 3428 KB Output is correct
8 Correct 121 ms 3428 KB Output is correct
9 Correct 139 ms 3428 KB Output is correct
10 Correct 134 ms 3428 KB Output is correct
11 Correct 137 ms 3428 KB Output is correct
12 Correct 127 ms 3428 KB Output is correct
13 Correct 130 ms 3428 KB Output is correct
14 Correct 133 ms 3428 KB Output is correct
15 Correct 38 ms 3428 KB Output is correct
16 Correct 88 ms 3428 KB Output is correct
17 Correct 138 ms 3428 KB Output is correct