QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87838 | #5740. Testing Subjects Usually Die | xiaoyaowudi | WA | 2ms | 3544kb | C++17 | 1.7kb | 2023-03-14 15:08:04 | 2023-03-14 15:10:02 |
Judging History
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'