Submission #1272498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272498		witek_cpp	Let's Win the Election (JOI22_ho_t3)	C++20	10 / 100	1 ms	348 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ld = long double;
const ld INF = 1e30L;

struct Fenwick {
    int n;
    vector<long long> cnt;    // counts (integral)
    vector<ld> sum;           // sums (long double)
    Fenwick(int n=0){ init(n); }
    void init(int n_){
        n = n_;
        cnt.assign(n+1,0);
        sum.assign(n+1,0);
    }
    void add(int i, long long dc, ld ds){
        for(; i<=n; i += i&-i){
            cnt[i] += dc;
            sum[i] += ds;
        }
    }
    long long pref_cnt(int i){
        long long r=0;
        for(; i>0; i-=i&-i) r+=cnt[i];
        return r;
    }
    ld pref_sum(int i){
        ld r=0;
        for(; i>0; i-=i&-i) r+=sum[i];
        return r;
    }
    // find smallest idx such that pref_cnt(idx) >= need (1-based), or n+1 if not enough
    int find_by_count(long long need){
        if(need <= 0) return 0;
        long long cur = 0;
        int pos = 0;
        int LOG = 1;
        while((1<<LOG) <= n) ++LOG;
        for(int k = LOG; k >= 0; --k){
            int nxt = pos + (1<<k);
            if(nxt <= n && cur + cnt[nxt] < need){
                pos = nxt;
                cur += cnt[nxt];
            }
        }
        return pos+1; // pos is last with sum < need
    }
    long long total_cnt(){ return pref_cnt(n); }
    ld total_sum(){ return pref_sum(n); }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, K;
    if(!(cin >> n >> K)) return 0;
    vector<ld> Aorig(n);
    vector<ld> Borig(n);
    for(int i=0;i<n;i++){
        long long Ai; long long Bi;
        cin >> Ai >> Bi;
        Aorig[i] = (ld)Ai;
        if(Bi == -1) Borig[i] = INF;
        else Borig[i] = (ld)Bi;
    }

    // pair by B then A
    vector<pair<ld,ld>> v;
    v.reserve(n);
    for(int i=0;i<n;i++) v.push_back({Borig[i], Aorig[i]});
    sort(v.begin(), v.end()); // rosnaco po B

    vector<ld> B(n+1), A(n+1);
    for(int i=0;i<n;i++){
        B[i+1] = v[i].first;
        A[i+1] = v[i].second;
    }

    // prefix sum of B_j / j
    vector<ld> prefBdiv(n+1, 0.0L);
    for(int j=1;j<=n;j++){
        prefBdiv[j] = prefBdiv[j-1] + B[j] / (ld)j;
    }

    // prepare compression for A values (we will only ever store A[1..n])
    vector<ld> allA;
    allA.reserve(n);
    for(int i=1;i<=n;i++) allA.push_back(A[i]);
    sort(allA.begin(), allA.end());
    allA.erase(unique(allA.begin(), allA.end(), [](ld x, ld y){ return fabsl(x-y) < 1e-12L; }), allA.end());
    int M = (int)allA.size();

    auto get_rank = [&](ld x)->int{
        // 1-based rank of x in allA
        int pos = int(lower_bound(allA.begin(), allA.end(), x - 1e-18L) - allA.begin());
        return pos+1;
    };

    // build Fenwick with all A initially (we will remove helpers as m grows)
    Fenwick bit(M);
    for(int i=1;i<=n;i++){
        int r = get_rank(A[i]);
        bit.add(r, 1, A[i]);
    }

    // count how many helpers are actually available (B < INF)
    int num_helpers = 0;
    for(int i=1;i<=n;i++) if(B[i] < INF/2) num_helpers++;
    int max_m = min(num_helpers, max(0, K-1)); // nie ma sensu brać więcej niż K-1 pomagierów

    ld answer = 1e100L;
    // dla m = 0: nie usuwamy nic, czas zakupu = 0, potem wybieramy K smallest A z całego zbioru
    for(int m = 0; m <= max_m; ++m){
        // jeżeli m>0: usuwamy element A[m] (bo ten stan stał się pomagierem)
        if(m > 0){
            int rnk = get_rank(A[m]); // m-th after sort by B
            bit.add(rnk, -1, -A[m]);
        }
        // czas zakupu pierwszych m pomagierów:
        ld time_buy = prefBdiv[m]; // sum_{j=1..m} B[j] / j

        int votes_from_helpers = m; // bo dla wybranych pomagierów Ai <= Bi
        int need = max(0, K - votes_from_helpers);
        if(need == 0){
            answer = min(answer, time_buy);
            continue;
        }
        if((long long)bit.total_cnt() < need) continue; // za malo pozostalych stanow -> niemozliwe

        // znajdź sumę najmniejszych 'need' A w bieżącym zbiorze (pozostałe nie-kupione)
        int idx = bit.find_by_count(need);
        // sum do idx-1 w pełni + ewentualnie kilka z idx jeśli duplikaty
        long long cnt_before = bit.pref_cnt(idx-1);
        ld sum_before = bit.pref_sum(idx-1);
        long long take_from_idx = need - cnt_before;
        ld val_idx = allA[idx-1]; // allA jest 0-based, idx jest 1-based
        ld sum_need = sum_before + val_idx * (ld)take_from_idx;

        ld time_votes = sum_need / (ld)(m+1);
        ld total_time = time_buy + time_votes;
        answer = min(answer, total_time);
    }

    cout.setf(std::ios::fixed);
    cout << setprecision(9) << (double)answer << "\n";
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23