623D - Birthday - CodeForces Solution

#include <cstdio>
#include <queue>
#include <vector>

using fp = long double;

int main()
{
	int N;
	scanf("%d", &N);
	std::vector<fp> p(N);
	for(int i=0;i<N;++i)
	{
		int x;
		scanf("%d", &x);
		p[i] = (fp)x/100;
	}

	fp ans = (fp)N;
	std::vector<fp> pprod(N);
	std::vector<fp> gain(N);

	fp opt = 1;
	for(int i=0;i<N;++i)
	{
		opt *= 1 - (pprod[i] = (1 - p[i]));
		gain[i] = (1 - pprod[i] * (1 - p[i])) / (1 - pprod[i]);
	}

	auto cmp = [&](int a, int b) {return gain[a] < gain[b];};

	std::priority_queue<int, std::vector<int>, decltype(cmp)> q(cmp);
	for(int i=0;i<N;++i) q.push(i);

	ans += 1 - opt;
	for(int t=0;t<1000000;++t)
	{
		int v = q.top();
		q.pop();
		opt *= gain[v];
		pprod[v] *= (1 - p[v]);
		ans += 1 - opt;

		gain[v] = (1 - pprod[v] * (1 - p[v])) / (1 - pprod[v]);
		q.push(v);
	}
	printf("%.9lf\n", (double)ans);
	return 0;
}