QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#182743#5740. Testing Subjects Usually Dieucup-team1209#WA 0ms4068kbC++202.1kb2023-09-18 14:52:582023-09-18 14:52:59

Judging History

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

  • [2023-09-18 14:52:59]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4068kb
  • [2023-09-18 14:52:58]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
#define templ template<typename T>
templ bool chkmin(T &x,T y){return x>y?x=y,1:0;}
templ bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
    #ifdef zqj
    freopen("a.in","r",stdin);
    #endif
}
typedef long long ll;
typedef long double db;
#define sz 101010

int n; db c;
db p[sz];

db calc(vector<db>k,vector<db>b) {
    vector<int>id(n);
    vector<db>tt(n);
    rep(i,0,n-1) id[i]=i,chkmax(b[i],1e-114L),tt[i]=k[i]/b[i]/b[i];
    sort(id.begin(),id.end(),[&](int x,int y){return tt[x]<tt[y];});
    db s1=0,s2=0;
    for (auto kk:k) s1+=sqrt(1/kk);
    rep(i,0,n-1) s2+=b[i]/k[i];
    s2++;
    db C=s1/s2;
    int L=0;
    while (233) {
        if (C*C<tt[id[L]]-1e-3) break;
        assert(L!=n-1);
        int x=id[L];
        s1-=sqrt(1/k[x]),s2-=b[x]/k[x];
        C=s1/s2;
        ++L;
    }
    C=C*C;
    vector<db>x(L);
    db s3=0;
    rep(i,L,n-1) x.push_back({(sqrt(k[i]/C)-b[i])/k[i]}),s3+=x.back();
    // assert(fabs(s3-1)<1e-8);
    db res=0;
    rep(i,0,n-1) res+=1/(k[i]*x[i]+b[i]);
    return res;
}

db check(db a) {
    vector<db>k,b;
    db res=0;
    rep(i,1,n) {
        res-=p[i]*c*a/(1-c);
        db K=(1-c)*(1-c),B=(1-c)*c;
        K/=p[i],B/=p[i];
        K/=(1+c*a-c),B/=(1+c*a-c);
        k.push_back(K),b.push_back(B);
    }
    res+=calc(k,b);
    return res;
}

int main() {
    file();
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>c;
    rep(i,1,n) cin>>p[i],p[sz-1]+=p[i];
    rep(i,1,n) p[i]/=p[sz-1];
    if (c==100) {
        db mx=0;
        rep(i,1,n) chkmax(mx,p[i]);
        cout<<setprecision(10)<<fixed<<1/mx<<'\n';
        return 0;
    }
    // TODO: c=0?
    c/=100;
    db l=0,r=n;
    rep(i,1,100) {
        db m=(l+r)/2;
        if (check(m)<=m) r=m;
        else l=m;
    }
    cout<<setprecision(10)<<fixed<<(l+r)/2<<'\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3848kb

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: 0ms
memory: 3816kb

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: 0ms
memory: 3948kb

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: 0
Accepted
time: 0ms
memory: 4068kb

input:

5 10
85 144 62 67 925

output:

3.0823373302

result:

ok found '3.0823373', expected '3.0823373', error '0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

5 20
573 598 705 893 279

output:

4.6655640734

result:

ok found '4.6655641', expected '4.6655641', error '0.0000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

5 25
533 195 166 109 527

output:

3.9338079305

result:

ok found '3.9338079', expected '3.9338079', error '0.0000000'

Test #7:

score: -100
Wrong Answer
time: 0ms
memory: 4052kb

input:

5 50
498 942 71 637 663

output:

5.0000000000

result:

wrong answer 1st numbers differ - expected: '3.8718857', found: '5.0000000', error = '0.2913604'