Submission #607168

#	Time	Username	Problem	Language	Result	Execution time	Memory
607168		jophyyjh	Sure Bet (CEOI17_sure)	C++14	100 / 100	1715 ms	5192 KiB

sure

/**
 * 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 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40