QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87838#5740. Testing Subjects Usually DiexiaoyaowudiWA 2ms3544kbC++171.7kb2023-03-14 15:08:042023-03-14 15:10:02

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-14 15:10:02]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3544kb
  • [2023-03-14 15:08:04]
  • 提交

answer

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cmath>
constexpr int N(1e5+10);
using ld=long double;
constexpr ld eps(1e-14);
int pi[N],sp,n,c,mp,np;
bool check(ld k)
{
	ld b(ld(c)/100);ld mc(-(1-b)/b*k),t(k*(1-b)*(1-b)/b+1+k*(1-b));
	ld cr(-t*b),cl(-t*b/(1-b)/(1-b));
	ld l(cl*mp/sp),r(cr*np/sp),mid;
	ld lim(ld(1)/(1-b)/(1-b));
	while(r-l>eps)
	{
		mid=(l+r)/2;ld tot(mc);
		ld tr(-mid/t/b);
		for(int i(1);i<=n;++i)
		{
			ld v(tr/pi[i]*sp);
			if(v<1) tot+=1;
			else if(v<lim) tot+=(std::sqrt(1/lim)-(1-b))/b;
		}
		if(tot<1) l=mid;
		else r=mid;
	}
	ld tr(-l/t/b);ld ans(mc);
	for(int i(1);i<=n;++i)
	{
		ld v(tr/pi[i]*sp);
		if(v<1) ans+=t*pi[i]/sp/*,std::cerr<<1<<","<<t+mc<<" "*/;
		else if(v<lim)
		{
			ld x((std::sqrt(1/lim)-(1-b))/b);
			// std::cerr<<x<<","<<t/(1-b+b*x)+mc<<" ";
			ans+=t/(1-b+b*x)*pi[i]/sp;
		}
		else ans+=t/(1-b)*pi[i]/sp/*,std::cerr<<0<<","<<t/(1-b)+mc<<" "*/;
	}
	// std::cerr<<l<<" "<<ans<<std::endl;
	return ans<=k;
}
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin>>n>>c;c=100-c;
	for(int i(1);i<=n;++i) std::cin>>pi[i],sp+=pi[i];
	mp=*std::max_element(pi+1,pi+n+1);np=*std::min_element(pi+1,pi+n+1);
	std::cout<<std::fixed<<std::setprecision(10);
	std::cerr<<std::fixed<<std::setprecision(10);
	if(!c)
	{
		std::cout<<ld(sp)/mp<<std::endl;
		return 0;
	}
	else if(c==100)
	{
		ld ans(0),tot(0);for(int i(1);i<=n;++i) tot+=std::sqrt(ld(pi[i])/sp);
		for(int i(1);i<=n;++i) ans+=ld(pi[i])/sp/(std::sqrt(ld(pi[i])/sp)/tot);
		std::cout<<ans<<std::endl;
		return 0;
	}
	ld l(1),r(1ll*n*n),mid;
	while(r-l>eps)
	{
		mid=(l+r)/2;
		if(check(mid)) r=mid;
		else l=mid;
	}
	std::cout<<l<<std::endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3544kb

input:

4 100
25 25 25 25

output:

4.0000000000

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3456kb

input:

2 0
1 4

output:

1.8000000000

result:

ok found '1.8000000', expected '1.8000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3456kb

input:

5 0
245 802 95 452 756

output:

4.4685309985

result:

ok found '4.4685310', expected '4.4685310', error '0.0000000'

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 3496kb

input:

5 10
85 144 62 67 925

output:

4.8702702703

result:

wrong answer 1st numbers differ - expected: '3.0823373', found: '4.8702703', error = '0.5800575'