Submission #1201078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201078		vincentbucourt1	Let's Win the Election (JOI22_ho_t3)	C++20	10 / 100	0 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long
#define ld long double

const int INF = (int)1e18;

int N, K;
struct Val{int vote, colab;};
bool cmpVal (const Val& a, const Val& b) {
    if (a.colab == -1) return false;
    else if (b.colab == -1) return true;
    else return tie(a.colab, a.vote) < tie(b.colab, b.vote);
}
vector<Val> vals;
ld ans = (ld)INF;

struct Segtree {
    int numleaves;
    vector<int> numVals, sumVals;
    Segtree (int n) {
        numleaves = 1;
        while (numleaves < n) numleaves *= 2;
        numVals.assign(2*numleaves, 0);
        sumVals.assign(2*numleaves, 0);
    }
    int query (int x) {
        int node = 1;
        int numBef = 0, sumBef = 0;
        while (numleaves > node) {
            if (numBef + numVals[2*node] >= x) {
                node = 2*node;
            }
            else {
                numBef += numVals[2*node];
                sumBef += sumVals[2*node];
                node = 2*node+1;
            }
        }
        sumBef += (x-numBef)*(node-numleaves);
        return sumBef;
    }
    void update (int idx, int sign) {
        idx += numleaves;
        numVals[idx] += sign;
        sumVals[idx] += sign*(idx-numleaves);
        idx /= 2;
        while (idx > 0) {
            numVals[idx] = numVals[2*idx] + numVals[2*idx+1];
            sumVals[idx] = sumVals[2*idx] + sumVals[2*idx+1];
            idx /= 2;
        }
    }
};

signed main() {
    fastIO();
    cin >> N >> K;
    vals.resize(N);
    Segtree sumQ(1020);
    for (int i = 0; i < N; i++) {
        cin >> vals[i].vote >> vals[i].colab;
        sumQ.update(vals[i].vote, 1);
    }
    sort(vals.begin(), vals.end(), cmpVal);
    // for (int i = 0; i < (int)vals.size(); i++) cerr << vals[i].colab << " ";
    // cerr << "\n";
    ld sumColab = 0;
    ans = min(ans, (ld)sumQ.query(K));
    for (int i = 0; i < K && vals[i].colab != -1; i++) {
        sumColab += ((ld)vals[i].colab) / ((ld)(i + 1));
        sumQ.update(vals[i].vote, -1);
        ld sumVote = ((ld)sumQ.query(K-i-1)) / ((ld)(i + 2));
        ans = min(ans, sumColab + sumVote);
    }
    cout << fixed << setprecision(12) << ans << "\n";
}

• 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