oj.uz

Submission #14366

# Submission time Handle Problem Language Result Execution time Memory
14366 2015-05-12T15:26:21 Z Fakeable Be Two Bees (OJUZ10_b2b) C++
0 / 100
 137 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],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;
    }
    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 Incorrect 0 ms 3428 KB Output isn't correct
2 Correct 1 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
0.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 Incorrect 0 ms 3428 KB Output isn't correct
4 Correct 0 ms 3428 KB Output is correct
5 Correct 0 ms 3428 KB Output is correct
6 Correct 2 ms 3428 KB Output is correct
7 Correct 2 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
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 3428 KB Output is correct
2 Incorrect 64 ms 3428 KB Output isn't correct
3 Correct 125 ms 3428 KB Output is correct
4 Correct 134 ms 3428 KB Output is correct
5 Correct 88 ms 3428 KB Output is correct
6 Correct 129 ms 3428 KB Output is correct
7 Incorrect 129 ms 3428 KB Output isn't correct
8 Incorrect 73 ms 3428 KB Output isn't correct
9 Correct 129 ms 3428 KB Output is correct
10 Correct 40 ms 3428 KB Output is correct
11 Correct 81 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 132 ms 3428 KB Output is correct
2 Correct 125 ms 3428 KB Output is correct
3 Correct 135 ms 3428 KB Output is correct
4 Correct 137 ms 3428 KB Output is correct
5 Correct 131 ms 3428 KB Output is correct
6 Correct 136 ms 3428 KB Output is correct
7 Correct 92 ms 3428 KB Output is correct
8 Correct 132 ms 3428 KB Output is correct
9 Correct 134 ms 3428 KB Output is correct
10 Correct 130 ms 3428 KB Output is correct
11 Correct 136 ms 3428 KB Output is correct
12 Correct 131 ms 3428 KB Output is correct
13 Incorrect 79 ms 3428 KB Output isn't correct
14 Correct 45 ms 3428 KB Output is correct
15 Correct 126 ms 3428 KB Output is correct
16 Correct 132 ms 3428 KB Output is correct
17 Correct 90 ms 3428 KB Output is correct