oj.uz

Submission #14367

# Submission time Handle Problem Language Result Execution time Memory
14367 2015-05-13T00:03:07 Z Fakeable Be Two Bees (OJUZ10_b2b) C++
0 / 100
 136 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].second >= (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
0.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 Incorrect 0 ms 3428 KB Output isn't correct
6 Correct 0 ms 3428 KB Output is correct
7 Correct 0 ms 3428 KB Output is correct

Subtask #2
0.0 / 22.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 2 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 0 ms 3428 KB Output is correct
7 Incorrect 0 ms 3428 KB Output isn't correct
8 Correct 2 ms 3428 KB Output is correct
9 Correct 0 ms 3428 KB Output is correct

Subtask #3
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 3428 KB Output is correct
2 Correct 130 ms 3428 KB Output is correct
3 Correct 60 ms 3428 KB Output is correct
4 Correct 45 ms 3428 KB Output is correct
5 Correct 135 ms 3428 KB Output is correct
6 Correct 93 ms 3428 KB Output is correct
7 Correct 130 ms 3428 KB Output is correct
8 Correct 134 ms 3428 KB Output is correct
9 Incorrect 125 ms 3428 KB Output isn't correct
10 Correct 77 ms 3428 KB Output is correct
11 Correct 80 ms 3428 KB Output is correct
12 Correct 129 ms 3428 KB Output is correct

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 3428 KB Output is correct
2 Correct 131 ms 3428 KB Output is correct
3 Correct 133 ms 3428 KB Output is correct
4 Correct 130 ms 3428 KB Output is correct
5 Correct 46 ms 3428 KB Output is correct
6 Correct 122 ms 3428 KB Output is correct
7 Incorrect 132 ms 3428 KB Output isn't correct
8 Correct 130 ms 3428 KB Output is correct
9 Correct 136 ms 3428 KB Output is correct
10 Correct 132 ms 3428 KB Output is correct
11 Incorrect 128 ms 3428 KB Output isn't correct
12 Correct 93 ms 3428 KB Output is correct
13 Correct 125 ms 3428 KB Output is correct
14 Correct 132 ms 3428 KB Output is correct
15 Correct 133 ms 3428 KB Output is correct
16 Correct 93 ms 3428 KB Output is correct
17 Correct 133 ms 3428 KB Output is correct