QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#737928 | #8027. Sky Garden | ucup-team3474 | AC ✓ | 594ms | 10428kb | C++20 | 1.6kb | 2024-11-12 17:11:51 | 2024-11-12 17:11:52 |
Judging History
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,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
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