QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#737928#8027. Sky Gardenucup-team3474AC ✓594ms10428kbC++201.6kb2024-11-12 17:11:512024-11-12 17:11:52

Judging History

This is the latest submission verdict.

  • [2024-11-12 17:11:52]
  • Judged
  • Verdict: AC
  • Time: 594ms
  • Memory: 10428kb
  • [2024-11-12 17:11:51]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;
const double PI=acos(-1);
typedef long long ll;
int n,m;

double  c[514];


double val[514];

vector<pair<int,double>> e[500010];

double d[500010];
bool tf[500010];


void dijkstra(int x){
    priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>> q;
    q.push({0,x});
    d[x]=0;
    while(q.size()){
        auto t=q.top();
        q.pop();
        if(tf[t.second]) continue;
        tf[t.second]=1;
        for(auto [j,w]:e[t.second]){
            if(d[j]>d[t.second]+w)
            {
                d[j]=d[t.second]+w;;
                q.push({d[j],j});
            }
        }
    }
}

signed main() {
    cin>>n>>m;

    double ans=0;
    m*=2;
    int j=1;
    // double ans=0;
    for(int i=1;i<=n;i++){
        
        j+=m;
        for(int k=0;k<=j;k++) d[k]=1e9,tf[k]=0;
        
        d[j-1]=0;
        int base=j-1;
        base--;
        int R=base/m+1,C=base%m;
        for(int k=j-2;k>0;k--){
            int r=(k-1)/m+1,c=(k-1)%m;
            double d1=R-r+PI*2*r/m*min(m-abs(C-c),abs(C-c));
            double d2=R+r;
            // printf("%.15lf %.15lf\n",d1,d2);
            d[k]=min(d1,d2);
        }

        for(int k=1;k<j-m;k++) ans+=m*d[k];
        if(m!=2)
        ans+=m*i;
        double res=0;
        // cout<<j-m+1<<endl;
        for(int k=j-m;k<j;k++) res+=d[k];
        // for(int k=0;k<j;k++) printf("%.15f ",d[k]);
        // cout<<endl;
        res/=2;
        ans+=m*res;
    }
    printf("%.15f",ans);
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

input:

1 2

output:

14.283185307179586

result:

ok found '14.2831853', expected '14.2831853', error '0.0000000'

Test #2:

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

input:

1 1

output:

2.000000000000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #3:

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

input:

500 1

output:

166916500.000000000000000

result:

ok found '166916500.0000000', expected '166916500.0000000', error '0.0000000'

Test #4:

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

input:

500 2

output:

763585309.561452269554138

result:

ok found '763585309.5614523', expected '763585309.5613225', error '0.0000000'

Test #5:

score: 0
Accepted
time: 589ms
memory: 8432kb

input:

500 499

output:

49125277129744.046875000000000

result:

ok found '49125277129744.0468750', expected '49125277129819.2734375', error '0.0000000'

Test #6:

score: 0
Accepted
time: 594ms
memory: 10428kb

input:

500 500

output:

49322369986184.554687500000000

result:

ok found '49322369986184.5546875', expected '49322369986259.6953125', error '0.0000000'

Test #7:

score: 0
Accepted
time: 43ms
memory: 4352kb

input:

252 139

output:

488838606007.174560546875000

result:

ok found '488838606007.1745605', expected '488838606007.1795654', error '0.0000000'

Test #8:

score: 0
Accepted
time: 17ms
memory: 5876kb

input:

96 359

output:

181277190205.008117675781250

result:

ok found '181277190205.0081177', expected '181277190205.0371094', error '0.0000000'

Test #9:

score: 0
Accepted
time: 130ms
memory: 8160kb

input:

237 487

output:

4992630041176.396484375000000

result:

ok found '4992630041176.3964844', expected '4992630041184.1953125', error '0.0000000'

Test #10:

score: 0
Accepted
time: 14ms
memory: 4448kb

input:

81 411

output:

142953582310.242889404296875

result:

ok found '142953582310.2428894', expected '142953582310.2773743', error '0.0000000'

Test #11:

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

input:

221 39

output:

25968641931.510841369628906

result:

ok found '25968641931.5108414', expected '25968641931.5297089', error '0.0000000'

Test #12:

score: 0
Accepted
time: 86ms
memory: 5128kb

input:

270 259

output:

2087014641696.235107421875000

result:

ok found '2087014641696.2351074', expected '2087014641700.0227051', error '0.0000000'

Test #13:

score: 0
Accepted
time: 330ms
memory: 8240kb

input:

422 387

output:

17770193032337.085937500000000

result:

ok found '17770193032337.0859375', expected '17770193032349.6250000', error '0.0000000'

Test #14:

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

input:

63 15

output:

89852047.508520171046257

result:

ok found '89852047.5085202', expected '89852047.5085171', error '0.0000000'

Test #15:

score: 0
Accepted
time: 347ms
memory: 8304kb

input:

407 439

output:

20515296102927.238281250000000

result:

ok found '20515296102927.2382812', expected '20515296102923.2070312', error '0.0000000'

Test #16:

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

input:

18 18

output:

3123573.695647549349815

result:

ok found '3123573.6956475', expected '3123573.6956476', error '0.0000000'

Test #17:

score: 0
Accepted
time: 22ms
memory: 4520kb

input:

171 146

output:

168786179166.977874755859375

result:

ok found '168786179166.9778748', expected '168786179167.0194092', error '0.0000000'

Test #18:

score: 0
Accepted
time: 29ms
memory: 6052kb

input:

311 70

output:

232875509505.215148925781250

result:

ok found '232875509505.2151489', expected '232875509505.2748413', error '0.0000000'

Test #19:

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

input:

155 494

output:

1439825967581.958496093750000

result:

ok found '1439825967581.9584961', expected '1439825967582.9992676', error '0.0000000'

Test #20:

score: 0
Accepted
time: 84ms
memory: 7140kb

input:

204 418

output:

2347066265472.008300781250000

result:

ok found '2347066265472.0083008', expected '2347066265474.4873047', error '0.0000000'

Test #21:

score: 0
Accepted
time: 26ms
memory: 3932kb

input:

344 46

output:

136054690372.238220214843750

result:

ok found '136054690372.2382202', expected '136054690372.2714844', error '0.0000000'

Test #22:

score: 0
Accepted
time: 30ms
memory: 6124kb

input:

188 174

output:

318429902144.993225097656250

result:

ok found '318429902144.9932251', expected '318429902145.0420532', error '0.0000000'

Test #23:

score: 0
Accepted
time: 32ms
memory: 5040kb

input:

137 394

output:

632896487875.993774414062500

result:

ok found '632896487875.9937744', expected '632896487876.0313721', error '0.0000000'

Test #24:

score: 0
Accepted
time: 25ms
memory: 4088kb

input:

481 22

output:

85020954588.178527832031250

result:

ok found '85020954588.1785278', expected '85020954588.2031097', error '0.0000000'

Test #25:

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

input:

30 446

output:

8705279441.350694656372070

result:

ok found '8705279441.3506947', expected '8705279441.3520851', error '0.0000000'

Test #26:

score: 0
Accepted
time: 88ms
memory: 6244kb

input:

204 440

output:

2600626525624.221679687500000

result:

ok found '2600626525624.2216797', expected '2600626525627.9575195', error '0.0000000'

Test #27:

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

input:

2 3

output:

175.415926535897938

result:

ok found '175.4159265', expected '175.4159265', error '0.0000000'

Extra Test:

score: 0
Extra Test Passed