Submission #1288238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288238		tunademayo	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 ll = long long;
struct Fenwick {
    int n;
    vector<long double> bitSum;
    vector<int> bitCnt;
    Fenwick(int n=0){ init(n); }
    void init(int n_){
        n = n_;
        bitSum.assign(n+1, 0.0L);
        bitCnt.assign(n+1, 0);
    }
    void add(int idx, long double val, int cnt){
        for(int i = idx; i <= n; i += i & -i){
            bitSum[i] += val;
            bitCnt[i] += cnt;
        }
    }
    // prefix sum, prefix count
    long double sumPrefix(int idx){
        long double s = 0;
        for(int i = idx; i > 0; i -= i & -i) s += bitSum[i];
        return s;
    }
    int cntPrefix(int idx){
        int s = 0;
        for(int i = idx; i > 0; i -= i & -i) s += bitCnt[i];
        return s;
    }
    // find smallest position p such that cntPrefix(p) >= k. assume k >= 1 and k <= total count
    int findByCount(int k){
        int pos = 0;
        int LOG = 1;
        while((1<<LOG) <= n) ++LOG;
        for(int pw = 1<<LOG; pw; pw >>= 1){
            if(pos + pw <= n && bitCnt[pos + pw] < k){
                k -= bitCnt[pos + pw];
                pos += pw;
            }
        }
        return pos + 1;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    if(!(cin >> N >> K)) return 0;
    vector<long double> A(N);
    vector<long double> B(N);
    for(int i=0;i<N;++i){
        ll ai, bi;
        cin >> ai >> bi;
        A[i] = (long double)ai;
        B[i] = (long double)bi; // bi == -1 means no collaborator
    }

    // collect collaborator candidates
    vector<pair<long double,int>> coll; // (Bi, idx)
    for(int i=0;i<N;++i) if(B[i] >= 0) coll.emplace_back(B[i], i);
    sort(coll.begin(), coll.end(), [](auto &p1, auto &p2){
        if(p1.first != p2.first) return p1.first < p2.first;
        return p1.second < p2.second;
    });

    // prepare Ai sorted list (value, idx)
    vector<pair<long double,int>> allA;
    allA.reserve(N);
    for(int i=0;i<N;++i) allA.emplace_back(A[i], i);
    sort(allA.begin(), allA.end());

    // Fenwick over sorted by Ai positions: initially include all states
    Fenwick fw(N);
    // position map: idx -> position in sorted allA (1-based)
    vector<int> pos(N);
    for(int i=0;i<N;++i){
        pos[allA[i].second] = i+1;
    }
    for(int i=0;i<N;++i){
        fw.add(i+1, (long double)allA[i].first, 1);
    }

    long double ans = 1e100L;
    int maxColl = (int)coll.size();
    int limit = min(K, maxColl);

    // We will iterate i = number of collaborators we will obtain (0..limit)
    // As we increase i, we remove that state's Ai from BIT (since it's already "used" and counted among votes)
    long double t0 = 0.0L; // prefix time to get i collaborators
    for(int i = 0; i <= limit; ++i){
        int haveVotesFromColl = i; // each collaborator state gives vote (Bi >= Ai guaranteed)
        int need = K - haveVotesFromColl;
        if(need <= 0){
            // already have >= K votes
            ans = min(ans, t0);
        } else {
            // check how many available states remain in BIT
            int available = fw.cntPrefix(N);
            if(available >= need){
                // get sum of smallest 'need' Ai among available
                int posK = fw.findByCount(need);
                int cntBefore = fw.cntPrefix(posK-1);
                long double sumBefore = fw.sumPrefix(posK-1);
                int takeAtPos = need - cntBefore;
                long double valAtPos = allA[posK-1].first;
                long double sumNeed = sumBefore + valAtPos * (long double)takeAtPos;
                long double totalTime = t0 + sumNeed / (1.0L + (long double)i);
                if(totalTime < ans) ans = totalTime;
            }
        }
        // prepare for next i: if i == limit we stop; otherwise include next collaborator (remove its Ai from BIT and add time to t0)
        if(i == limit) break;
        // collaborator to be obtained is coll[i] (0-based)
        long double Bi = coll[i].first;
        int idx = coll[i].second;
        // time to get this collaborator when currently have (1 + i) speakers: we must spend Bi / (1 + i) additional time
        // BUT we must consider cumulative effect: previously t0 already sum for earlier collaborators, so add Bi / (1+i)
        t0 += Bi / (1.0L + (long double)i);
        // This collaborator's Ai is already satisfied (Bi >= Ai), so remove its Ai from the pool if still present.
        int p = pos[idx];
        // check if still present (count at p might be 1)
        // safe to always attempt to remove; but need to ensure we only remove once
        // We'll query count prefix and single index count:
        // get count at single index by cntPrefix(p) - cntPrefix(p-1)
        int cntAt = fw.cntPrefix(p) - fw.cntPrefix(p-1);
        if(cntAt > 0){
            fw.add(p, - (long double)allA[p-1].first, -1);
        }
    }

    // print with required format; error tolerance <= 0.01
    cout.setf(std::ios::fixed); cout<<setprecision(12);
    double out = (double)ans;
    cout << out << "\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