QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#659087#5667. Meeting Placesucup-team5234WA 57ms3980kbC++232.9kb2024-10-19 18:33:452024-10-19 18:33:50

Judging History

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

  • [2024-10-19 18:33:50]
  • 评测
  • 测评结果:WA
  • 用时:57ms
  • 内存:3980kb
  • [2024-10-19 18:33:45]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
ll MOD = 1000000007;
ll INF = (1ll<<60);
using ld = long double;
#define rep(i,n) for(int i=0;i<n;i++)

#define dout(a) cout << fixed << setprecision(20) << a << endl;

ld dis(ld x, ld y) {
    return x*x + y*y;
}
static const ld eps = 1e-12;
tuple<ld, ld, ld> solve(vector<pair<ld, ld>> p){
    int n = p.size();
    ld x = 0, y = 0;
    rep(i, n) {
        x += p[i].first;
        y += p[i].second;
    }
    x /= ld(n);
    y /= ld(n);
    ld r = 0.992;
    ld d = 1e9;
    
    rep(_, 3000) {
        int id = -1;
        ld m = -1;
        rep(i, n) {
            ld ret = dis(x - p[i].first, y - p[i].second);
            if(ret > m) {
                m = ret;
                id = i;
            }
        }
        ld X = p[id].first - x;
        ld Y = p[id].second - y;
        m = sqrtl(m);
        X /= m;
        Y /= m;
        X *= d;
        Y *= d;
        x += X;
        y += Y;
        d *= r;
    }
    ld m = -eps;
    rep(i, n) {
        ld ret = dis(x - p[i].first, y - p[i].second);
        if(ret > m) {
            m = ret;
        }
    }
    return {sqrtl(m), x, y};
}

int main(){
    
    ll n,k,X;
    cin >> n >> k >> X;
    if(n == k){
        cout << 0.0 << endl;
        return 0;
    }

    vector<ld> x(n), y(n);
    rep(i,n){
        x[i] = X;
        X = X*233811181+1;
        X %= (1ll<<31)-1;
        y[i] = X;
        X = X*233811181+1;
        X %= (1ll<<31)-1;
    }

    ld ans = INF;
    if(n-k>10){
        ld sx, sy, sr;
        ld ep = 8;
        {
            vector<pair<ld, ld>> p;
            for(int j=0; j<n-k+1; j++) p.emplace_back(x[j], y[j]);
            auto[r, x, y] = solve(p);
            ans = min(ans, r);
            sx = x, sy = y, sr = r;

        }
        for(int i=1; i+n-k+1<=n; i++){
            ld R = sqrtl(dis(sx - x[i-1], sy - y[i-1]));
            ld R2 = sqrtl(dis(sx - x[i+n-k], sy - y[i+n-k]));
            if(R > sr - ep || R2 > sr){
                vector<pair<ld, ld>> p;
                for(int j=i; j<i+n-k+1; j++) p.emplace_back(x[j], y[j]);
                auto[a,b,c] = solve(p);
                ans = min(ans, a);
                sr = a;
                sx = b;
                sy = c;
            }
        }
    }else{
        vector<vector<ld>> dp(n+1, vector<ld>(10, 10000000000000000.0));
        dp[0][0] = 0.0;
        for(int i=0;i<n; i++){
            for(int j=0;j<10;j++) dp[i+1][j] = min(dp[i][j], dp[i+1][j]);
            for(int j=1;j<10&&i+j<n;j++){
                vector<pair<ld, ld>> p;
                for(int k=i; k<=i+j; k++) p.emplace_back(x[k], y[k]);
                auto[r,a,b] = solve(p);
                for(int k=0; k+j<10;k++) dp[i+j+1][k+j] = min(dp[i+j+1][k+j], dp[i][k]+r);
            }
        }
        ans = dp[n][n-k];
    }
    dout(ans);

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3832kb

input:

100 23 213

output:

1319350480.80100661958567798138

result:

ok found '1319350480.8010066', expected '1319350480.8007326', error '0.0000000'

Test #2:

score: 0
Accepted
time: 3ms
memory: 3756kb

input:

10 1 1060

output:

1042753143.34544635179918259382

result:

ok found '1042753143.3454463', expected '1042753143.3451676', error '0.0000000'

Test #3:

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

input:

10 10 2373

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #4:

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

input:

10 2 3396

output:

1236610536.94692303182091563940

result:

ok found '1236610536.9469230', expected '1236610536.9469230', error '0.0000000'

Test #5:

score: 0
Accepted
time: 3ms
memory: 3840kb

input:

10 3 1998

output:

973790809.82244437362533062696

result:

ok found '973790809.8224443', expected '973790809.8224442', error '0.0000000'

Test #6:

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

input:

10 4 562

output:

910867389.93145099864341318607

result:

ok found '910867389.9314510', expected '910867389.9069330', error '0.0000000'

Test #7:

score: 0
Accepted
time: 3ms
memory: 3780kb

input:

10 5 6048

output:

818240814.73565637960564345121

result:

ok found '818240814.7356564', expected '818240814.7105150', error '0.0000000'

Test #8:

score: 0
Accepted
time: 3ms
memory: 3828kb

input:

10 6 2524

output:

500106979.37403708405327051878

result:

ok found '500106979.3740371', expected '500106979.3467762', error '0.0000000'

Test #9:

score: 0
Accepted
time: 3ms
memory: 3892kb

input:

10 7 5415

output:

559478971.43228468077722936869

result:

ok found '559478971.4322847', expected '559478971.4320059', error '0.0000000'

Test #10:

score: 0
Accepted
time: 3ms
memory: 3896kb

input:

10 8 1438

output:

500309745.46276999477413482964

result:

ok found '500309745.4627700', expected '500309745.4627700', error '0.0000000'

Test #11:

score: 0
Accepted
time: 3ms
memory: 3844kb

input:

10 9 3172

output:

162279748.87534531218989286572

result:

ok found '162279748.8753453', expected '162279748.8753452', error '0.0000000'

Test #12:

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

input:

100 1 8316

output:

1320052902.15256890852469950914

result:

ok found '1320052902.1525688', expected '1320052902.1522903', error '0.0000000'

Test #13:

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

input:

100 100 4179

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #14:

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

input:

100 12 3405

output:

1329687126.13392433314584195614

result:

ok found '1329687126.1339242', expected '1329687126.1304548', error '0.0000000'

Test #15:

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

input:

100 16 8378

output:

1338056514.48426947277039289474

result:

ok found '1338056514.4842694', expected '1338056514.4842694', error '0.0000000'

Test #16:

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

input:

100 2 1858

output:

1310392496.14512442890554666519

result:

ok found '1310392496.1451244', expected '1310392496.1430581', error '0.0000000'

Test #17:

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

input:

100 25 4596

output:

1440464106.62320375256240367889

result:

ok found '1440464106.6232038', expected '1440464106.6229298', error '0.0000000'

Test #18:

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

input:

100 3 5633

output:

1399621082.61427382135298103094

result:

ok found '1399621082.6142738', expected '1399621082.6142738', error '0.0000000'

Test #19:

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

input:

100 32 7827

output:

1342073760.55519409885164350271

result:

ok found '1342073760.5551941', expected '1342073760.5322330', error '0.0000000'

Test #20:

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

input:

100 4 3693

output:

1339808706.71657487901393324137

result:

ok found '1339808706.7165749', expected '1339808706.7098689', error '0.0000000'

Test #21:

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

input:

100 5 2252

output:

1394874243.50570870633237063885

result:

ok found '1394874243.5057087', expected '1394874243.5057042', error '0.0000000'

Test #22:

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

input:

100 50 4254

output:

1322809748.44021508470177650452

result:

ok found '1322809748.4402151', expected '1322809748.4052832', error '0.0000000'

Test #23:

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

input:

100 6 53

output:

1364441356.20448634412605315447

result:

ok found '1364441356.2044864', expected '1364441356.1700988', error '0.0000000'

Test #24:

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

input:

100 64 4337

output:

1180754550.24636472587008029222

result:

ok found '1180754550.2463648', expected '1180754550.2422838', error '0.0000000'

Test #25:

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

input:

100 7 5366

output:

1423557626.36165848991367965937

result:

ok found '1423557626.3616586', expected '1423557626.3586798', error '0.0000000'

Test #26:

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

input:

100 8 8509

output:

1353289305.35253538575489073992

result:

ok found '1353289305.3525355', expected '1353289305.3519957', error '0.0000000'

Test #27:

score: 0
Accepted
time: 3ms
memory: 3764kb

input:

100 9 1423

output:

1228887266.59917310252785682678

result:

ok found '1228887266.5991731', expected '1228887266.5661671', error '0.0000000'

Test #28:

score: 0
Accepted
time: 56ms
memory: 3956kb

input:

100 91 4806

output:

656574218.52468914596829563379

result:

ok found '656574218.5246892', expected '656574218.5086756', error '0.0000000'

Test #29:

score: 0
Accepted
time: 56ms
memory: 3844kb

input:

100 92 4024

output:

794693428.63277634116820991039

result:

ok found '794693428.6327764', expected '794693428.6162238', error '0.0000000'

Test #30:

score: 0
Accepted
time: 56ms
memory: 3892kb

input:

100 93 606

output:

677641813.44694434193661436439

result:

ok found '677641813.4469444', expected '677641787.4863122', error '0.0000000'

Test #31:

score: 0
Accepted
time: 56ms
memory: 3952kb

input:

100 94 7265

output:

686423239.26287742052227258682

result:

ok found '686423239.2628775', expected '686423239.2626028', error '0.0000000'

Test #32:

score: 0
Accepted
time: 57ms
memory: 3860kb

input:

100 95 8469

output:

328187125.92359957654844038188

result:

ok found '328187125.9235996', expected '328187125.9235951', error '0.0000000'

Test #33:

score: 0
Accepted
time: 56ms
memory: 3832kb

input:

100 96 1079

output:

492964787.63024834616226144135

result:

ok found '492964787.6302484', expected '492964787.6259086', error '0.0000000'

Test #34:

score: 0
Accepted
time: 56ms
memory: 3800kb

input:

100 97 5453

output:

258652807.81889875022170599550

result:

ok found '258652807.8188987', expected '258652807.7906564', error '0.0000000'

Test #35:

score: 0
Accepted
time: 57ms
memory: 3828kb

input:

100 98 1778

output:

159490192.12737848640244919807

result:

ok found '159490192.1273785', expected '159490192.1188908', error '0.0000000'

Test #36:

score: 0
Accepted
time: 56ms
memory: 3860kb

input:

100 99 1825

output:

33793756.32899818097575916909

result:

ok found '33793756.3289982', expected '33793756.3289980', error '0.0000000'

Test #37:

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

input:

1000 1 2453

output:

1486878333.28613163670524954796

result:

ok found '1486878333.2861316', expected '1486878333.2858574', error '0.0000000'

Test #38:

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

input:

1000 1000 1798

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #39:

score: 0
Accepted
time: 5ms
memory: 3964kb

input:

1000 125 43

output:

1474031969.51813151955138891935

result:

ok found '1474031969.5181315', expected '1474031969.5174232', error '0.0000000'

Test #40:

score: -100
Wrong Answer
time: 15ms
memory: 3980kb

input:

1000 128 8107

output:

1440378279.91863670782186090946

result:

wrong answer 1st numbers differ - expected: '1440374614.9391975', found: '1440378279.9186368', error = '0.0000025'