oj.uz

Submission #14365

# Submission time Handle Problem Language Result Execution time Memory
14365 2015-05-12T15:19:58 Z Fakeable Be Two Bees (OJUZ10_b2b) C++
0 / 100
 1000 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;
    }
    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;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3428 KB Output is correct
2 Incorrect 1 ms 3428 KB Output isn't correct
3 Correct 0 ms 3428 KB Output is correct
4 Correct 0 ms 3428 KB Output is correct
5 Correct 1 ms 3428 KB Output is 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 4 ms 3428 KB Output is correct
2 Correct 6 ms 3428 KB Output is correct
3 Incorrect 0 ms 3428 KB Output isn't correct
4 Correct 16 ms 3428 KB Output is correct
5 Correct 16 ms 3428 KB Output is correct
6 Correct 12 ms 3428 KB Output is correct
7 Correct 15 ms 3428 KB Output is correct
8 Correct 16 ms 3428 KB Output is correct
9 Correct 15 ms 3428 KB Output is correct

Subtask #3
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 3428 KB Program timed out
2 Execution timed out 1000 ms 3424 KB Program timed out
3 Execution timed out 1000 ms 3424 KB Program timed out
4 Correct 760 ms 3428 KB Output is correct
5 Execution timed out 1000 ms 3424 KB Program timed out
6 Execution timed out 1000 ms 3424 KB Program timed out
7 Execution timed out 1000 ms 3424 KB Program timed out
8 Execution timed out 1000 ms 3428 KB Program timed out
9 Execution timed out 1000 ms 3428 KB Program timed out
10 Execution timed out 1000 ms 3424 KB Program timed out
11 Execution timed out 1000 ms 3428 KB Program timed out
12 Execution timed out 1000 ms 3428 KB Program timed out

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 3424 KB Program timed out
2 Execution timed out 1000 ms 3428 KB Program timed out
3 Correct 225 ms 3428 KB Output is correct
4 Execution timed out 1000 ms 3424 KB Program timed out
5 Execution timed out 1000 ms 3424 KB Program timed out
6 Execution timed out 1000 ms 3424 KB Program timed out
7 Execution timed out 1000 ms 3424 KB Program timed out
8 Execution timed out 1000 ms 3424 KB Program timed out
9 Execution timed out 1000 ms 3428 KB Program timed out
10 Execution timed out 1000 ms 3424 KB Program timed out
11 Execution timed out 1000 ms 3428 KB Program timed out
12 Execution timed out 1000 ms 3424 KB Program timed out
13 Execution timed out 1000 ms 3424 KB Program timed out
14 Execution timed out 1000 ms 3424 KB Program timed out
15 Execution timed out 1000 ms 3424 KB Program timed out
16 Execution timed out 1000 ms 3424 KB Program timed out
17 Execution timed out 1000 ms 3424 KB Program timed out