QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#182704#5740. Testing Subjects Usually Dieucup-team1209#WA 0ms4044kbC++201.7kb2023-09-18 14:12:572023-09-18 14:12:57

Judging History

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

  • [2023-09-18 14:12:57]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4044kb
  • [2023-09-18 14:12:57]
  • 提交

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 double db;
#define sz 101010

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

db calc(vector<db>k,vector<db>b) {
    int n=k.size();
    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; C*=C;
    vector<db>x;
    db s3=0;
    rep(i,0,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<<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: 4044kb

input:

4 100
25 25 25 25

output:

4

result:

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

Test #2:

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

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: 3972kb

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: 3928kb

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: 3948kb

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: 3804kb

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: 3752kb

input:

5 50
498 942 71 637 663

output:

2.9897285611

result:

wrong answer 1st numbers differ - expected: '3.8718857', found: '2.9897286', error = '0.2278366'