oj.uz

Submission #607168

# Submission time Handle Problem Language Result Execution time Memory
607168 2022-07-26T12:44:10 Z jophyyjh Sure Bet (CEOI17_sure) C++14
100 / 100
 1715 ms 5192 KB 
/**
 * Notes during contest.
 * 
 * ------ A ------
 * Looks like that it's about strongly-connected components, cycles or bridges. I
 * think we can detect all cycles and merge all those nodes into one. The resulting
 * graph would be a tree, so we can then use a difference array to find each edge's
 * direction. Note that any edge in a cycle is B, and any edge not in cycles is a
 * "bridge".
 *          !IMPORTANT! (Reminded by tinjyu during contest) !IMPORTANT!
 *                          Graph may not be CONNECTED.
 * 
 * ------ B ------
 * We iterate through all cost k. We can take at most k bets. If we can guarantee
 * a profit of p, min(#A_is_the_outcome, #B_is_the_outcome) >= p + k. Binary search
 * is ok.
 * For each k, we wanna find the max achievable for
 * min(#A_is_outcome, #B_is_outcome) - k.
 * 
 * ------ C ------
 * We have a tree in which a mouse runs. [S1] is just a brute-force.
 * 
 * Time Complexity 1: O(n + m + p * log(n))
 * Time Complexity 2: O(n * log(n * VAL_MAX) * log(n))
 * Time Complexity 3: O()
 * Implementation 1
*/
 
#include <bits/stdc++.h>
 
typedef int64_t     int_t;
typedef std::vector<int_t>  vec;
 
const double INF = 1e9;
const double VAL_MAX = 1e4;
 
 
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int_t n;
    std::cin >> n;
    std::vector<double> A(n), B(n);
    for (int_t k = 0; k < n; k++)
        std::cin >> A[k] >> B[k];
    
 
    std::sort(A.rbegin(), A.rend());
    std::sort(B.rbegin(), B.rend());
    std::vector<double> A_prefix(n + 1), B_prefix(n + 1);
    A_prefix[0] = B_prefix[0] = 0;
    for (int_t k = 0; k < n; k++)
        A_prefix[k + 1] = A_prefix[k] + A[k], B_prefix[k + 1] = B_prefix[k] + B[k];
    double profit = -INF;
    for (int_t cost = 0; cost <= 2 * n; cost++) {
        double min = 0;
        for (double step_m = n * VAL_MAX; step_m >= 0.000005; step_m /= 2) {
            for (;;) {
                double new_min = min + step_m;
 
                int_t A_used = n + 1;
                for (int_t step = n / 2 + 1; step >= 1; step /= 2) {
                    while (A_used - step >= 0 && A_prefix[A_used - step] >= new_min)
                        A_used -= step;
                }
                int_t B_used = n + 1;
                for (int_t step = n / 2 + 1; step >= 1; step /= 2) {
                    while (B_used - step >= 0 && B_prefix[B_used - step] >= new_min)
                        B_used -= step;
                }
                if (A_used == n + 1 || B_used == n + 1)
                    break;
                if (A_used + B_used <= cost)
                    min = new_min;
                else
                    break;
            }
        }
        // std::cerr << "[debug] " << cost << ": " << std::fixed << min << std::endl;
        profit = std::max(profit, min - cost);
    }
    std::cout << std::fixed << std::setprecision(4) << profit << '\n';
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 8 ms 340 KB Output is correct
13 Correct 9 ms 340 KB Output is correct
14 Correct 8 ms 368 KB Output is correct
15 Correct 10 ms 340 KB Output is correct
16 Correct 8 ms 340 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 8 ms 340 KB Output is correct
13 Correct 9 ms 340 KB Output is correct
14 Correct 8 ms 368 KB Output is correct
15 Correct 10 ms 340 KB Output is correct
16 Correct 8 ms 340 KB Output is correct
17 Correct 1690 ms 4808 KB Output is correct
18 Correct 1687 ms 4824 KB Output is correct
19 Correct 1647 ms 4820 KB Output is correct
20 Correct 1515 ms 4820 KB Output is correct
21 Correct 1613 ms 5192 KB Output is correct
22 Correct 1609 ms 4824 KB Output is correct
23 Correct 1598 ms 4816 KB Output is correct
24 Correct 1646 ms 4828 KB Output is correct
25 Correct 1487 ms 4824 KB Output is correct
26 Correct 1715 ms 5192 KB Output is correct