QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #707711 | #7753. Energy Distribution | qvzeyang | WA | 917ms | 3940kb | C++23 | 4.1kb | 2024-11-03 17:11:01 | 2024-11-03 17:11:02 |
Judging History
answer
#include<bits/stdc++.h>
namespace FRTMLV{
#define ll long long
//#define LD long double
#define i7 __int128
#define re return
#define con continue
using namespace std;
template<class T>inline bool ckmin(T &a,T b){re b<a?a=b,1:0;}
template<class T>inline bool ckmax(T &a,T b){re a<b?a=b,1:0;}
const int N=1e6+5;
inline int rd(){
int d=1,k=0;char c=getchar();
while(!(c>='0' and c<='9' or c=='-'))c=getchar();if(c=='-')d=-1,c=getchar();
while(c>='0' and c<='9')k=(k<<3)+(k<<1)+(c^48),c=getchar();
return d*k;
}
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
//mt19937 rnd(114514);
int n,w[11][11];
#define LD long double
LD e[11];
LD calc(){
LD ans=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)ans+=e[i]*e[j]*w[i][j];
re ans;
}
ll sum[11],Sum;
signed main(){
n=rd();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)w[i][j]=rd(),sum[i]+=w[i][j];
for(int i=1;i<=n;i++)Sum+=sum[i];
if(Sum==0){
puts("0.000000");re 0;
}
for(int i=1;i<=n;i++)e[i]=(LD)sum[i]/Sum;
LD mxans=calc();
for(int T=1;T<=1;T++){
LD ans;
for(int i=1;i<=n;i++)e[i]=(LD)sum[i]/Sum;
ans=calc();
// for(int i=1;i<=100000000;i++){
for(int i=1;i<=7000000;i++){
int u=rnd()%n+1,v=rnd()%n+1;
while(u==v)v=rnd()%n+1;
// LD x=(LD)1/sqrtl((ll)i*10000+2),k=x*e[u];
// LD x=(LD)1/min(((ll)i+100),10000ll),k=x*e[u];
LD x=(LD)1/((ll)i*2+100),k=x*e[u];
// LD x=(LD)1/sqrtl((ll)i+2),k=x*e[u];
LD det=(e[v]+k)*(e[u]-k)*w[u][v]-e[u]*e[v]*w[u][v];
for(int j=1;j<=n;j++){
if(j!=v&&j!=u){
det+=-k*e[j]*w[u][j]+k*e[j]*w[v][j];
}
}
if(det>0)e[v]+=k,e[u]-=k,ans+=det;
//
// e[v]+=k,e[u]-=k;
// if(!ckmax(ans,calc())){
// e[v]-=k,e[u]+=k;
// }
}
ckmax(mxans,ans);
}
for(int T=1;T<=1;T++){
LD ans;
for(int i=1;i<=n;i++)e[i]=(LD)sum[i]/Sum;
ans=calc();
// for(int i=1;i<=100000000;i++){
for(int i=1;i<=7000000;i++){
int u=rnd()%n+1,v=rnd()%n+1;
while(u==v)v=rnd()%n+1;
// LD x=(LD)1/sqrtl((ll)i*10000+2),k=x*e[u];
LD x=(LD)1/min(((ll)i+100),10000ll),k=x*e[u];
// LD x=(LD)1/((ll)i*2+100),k=x*e[u];
// LD x=(LD)1/sqrtl((ll)i+2),k=x*e[u];
LD det=(e[v]+k)*(e[u]-k)*w[u][v]-e[u]*e[v]*w[u][v];
for(int j=1;j<=n;j++){
if(j!=v&&j!=u){
det+=-k*e[j]*w[u][j]+k*e[j]*w[v][j];
}
}
if(det>0)e[v]+=k,e[u]-=k,ans+=det;
//
// e[v]+=k,e[u]-=k;
// if(!ckmax(ans,calc())){
// e[v]-=k,e[u]+=k;
// }
}
ckmax(mxans,ans);
}
for(int T=1;T<=1;T++){
LD ans;
for(int i=1;i<=n;i++)e[i]=(LD)sum[i]/Sum;
ans=calc();
// for(int i=1;i<=100000000;i++){
for(int i=1;i<=7000000;i++){
int u=rnd()%n+1,v=rnd()%n+1;
while(u==v)v=rnd()%n+1;
LD x=(LD)1/sqrtl((ll)i*10000+2),k=x*e[u];
// LD x=(LD)1/min(((ll)i+100),10000ll),k=x*e[u];
// LD x=(LD)1/((ll)i*2+100),k=x*e[u];
// LD x=(LD)1/sqrtl((ll)i+2),k=x*e[u];
LD det=(e[v]+k)*(e[u]-k)*w[u][v]-e[u]*e[v]*w[u][v];
for(int j=1;j<=n;j++){
if(j!=v&&j!=u){
det+=-k*e[j]*w[u][j]+k*e[j]*w[v][j];
}
}
if(det>0)e[v]+=k,e[u]-=k,ans+=det;
//
// e[v]+=k,e[u]-=k;
// if(!ckmax(ans,calc())){
// e[v]-=k,e[u]+=k;
// }
}
ckmax(mxans,ans);
}
printf("%.15Lf\n",mxans);
// printf("%.15lf\n",mxans);
// for(int i=1;i<=n;i++)printf("%.6lf ",e[i]);
re 0;
}
/*
3
0 2 1
2 0 2
1 2 0
10
0 114 1000 1000 45 1000 1000 1000 1000 1000
114 0 1000 1000 1000 1000 1000 1000 1 1000
1000 1000 0 1000 1000 1000 1000 233 1000 1000
1000 1000 1000 0 1000 1000 1000 1000 1000 1000
45 1000 1000 1000 0 1000 1000 1000 1000 1000
1000 1000 1000 1000 1000 0 999 1000 1000 1000
1000 1000 1000 1000 1000 999 0 1000 1000 1000
1000 1000 233 1000 1000 1000 1000 0 1000 1000
1000 1 1000 1000 1000 1000 1000 1000 0 1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 0
10
0 1 2 3 4 5 6 7 8 9
1 0 3 4 5 6 7 8 9 9
2 3 0 5 6 7 8 9 9 9
3 4 5 0 7 8 9 9 9 9
4 5 6 7 0 9 9 9 9 9
5 6 7 8 9 0 9 9 9 9
6 7 8 9 9 9 0 9 9 9
7 8 9 9 9 9 9 0 9 9
8 9 9 9 9 9 9 9 0 9
9 9 9 9 9 9 9 9 9 0
444.802902481672175 1
444.802902843977459 10
444.802902882372956 100
444.802902887373188 1000
*/
}signed main(){re FRTMLV::main();}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 757ms
memory: 3936kb
input:
2 0 1 1 0
output:
0.250000000000000
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 732ms
memory: 3940kb
input:
3 0 2 1 2 0 2 1 2 0
output:
0.571428571428570
result:
ok found '0.5714286', expected '0.5714290', error '0.0000004'
Test #3:
score: 0
Accepted
time: 767ms
memory: 3860kb
input:
3 0 1 2 1 0 1 2 1 0
output:
0.500000000000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 790ms
memory: 3916kb
input:
4 0 3 1 0 3 0 1 0 1 1 0 2 0 0 2 0
output:
0.749999999990963
result:
ok found '0.7500000', expected '0.7500000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 784ms
memory: 3940kb
input:
5 0 0 0 4 4 0 0 2 0 4 0 2 0 2 0 4 0 2 0 0 4 4 0 0 0
output:
1.000000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 792ms
memory: 3700kb
input:
6 0 9 5 5 10 6 9 0 0 0 0 1 5 0 0 0 3 0 5 0 0 0 10 5 10 0 3 10 0 0 6 1 0 5 0 0
output:
2.857142855694800
result:
ok found '2.8571429', expected '2.8571430', error '0.0000001'
Test #7:
score: 0
Accepted
time: 811ms
memory: 3796kb
input:
7 0 0 0 0 50 10 45 0 0 0 0 0 3 1 0 0 0 0 0 4 16 0 0 0 0 44 0 0 50 0 0 44 0 37 6 10 3 4 0 37 0 2 45 1 16 0 6 2 0
output:
12.511584800538760
result:
ok found '12.5115848', expected '12.5115850', error '0.0000000'
Test #8:
score: 0
Accepted
time: 828ms
memory: 3844kb
input:
8 0 0 56 0 0 58 16 0 0 0 37 20 0 82 0 0 56 37 0 0 98 0 83 0 0 20 0 0 0 0 100 0 0 0 98 0 0 62 29 0 58 82 0 0 62 0 43 0 16 0 83 100 29 43 0 4 0 0 0 0 0 0 4 0
output:
25.009117891430461
result:
ok found '25.0091179', expected '25.0091180', error '0.0000000'
Test #9:
score: 0
Accepted
time: 888ms
memory: 3940kb
input:
9 0 0 0 135 0 0 0 448 476 0 0 0 0 0 0 208 17 0 0 0 0 467 1 0 0 0 134 135 0 467 0 0 0 92 369 207 0 0 1 0 0 176 0 235 0 0 0 0 0 176 0 65 363 413 0 208 0 92 0 65 0 0 0 448 17 0 369 235 363 0 0 0 476 0 134 207 0 413 0 0 0
output:
118.999999867040132
result:
ok found '118.9999999', expected '119.0000000', error '0.0000000'
Test #10:
score: 0
Accepted
time: 917ms
memory: 3924kb
input:
10 0 0 0 289 0 397 0 0 140 155 0 0 28 101 35 614 0 0 545 300 0 28 0 0 329 702 0 242 0 298 289 101 0 0 0 0 0 0 720 0 0 35 329 0 0 0 0 38 0 0 397 614 702 0 0 0 229 0 0 0 0 0 0 0 0 229 0 317 0 0 0 0 242 0 38 0 317 0 961 309 140 545 0 720 0 0 0 961 0 92 155 300 298 0 0 0 0 309 92 0
output:
240.249986578746594
result:
ok found '240.2499866', expected '240.2500000', error '0.0000001'
Test #11:
score: 0
Accepted
time: 914ms
memory: 3884kb
input:
10 0 295 2 809 333 880 284 305 41 295 295 0 512 1000 281 153 42 550 962 930 2 512 0 727 709 969 665 973 301 410 809 1000 727 0 282 551 960 804 274 956 333 281 709 282 0 613 505 406 896 441 880 153 969 551 613 0 769 770 40 288 284 42 665 960 505 769 0 919 989 490 305 550 973 804 406 770 919 0 400 209...
output:
327.373658870491268
result:
ok found '327.3736589', expected '327.3736590', error '0.0000000'
Test #12:
score: 0
Accepted
time: 907ms
memory: 3868kb
input:
10 0 403 2 164 0 399 279 156 109 472 403 0 292 279 100 326 153 124 103 426 2 292 0 0 58 87 0 177 324 334 164 279 0 0 256 188 0 257 467 23 0 100 58 256 0 453 75 21 0 309 399 326 87 188 453 0 0 319 395 434 279 153 0 0 75 0 0 342 431 72 156 124 177 257 21 319 342 0 265 0 109 103 324 467 0 395 431 265 0...
output:
155.370358082311227
result:
ok found '155.3703581', expected '155.3703580', error '0.0000000'
Test #13:
score: 0
Accepted
time: 913ms
memory: 3852kb
input:
10 0 3 10 8 0 3 3 8 9 6 3 0 6 10 0 10 9 9 4 9 10 6 0 7 1 5 6 8 0 0 8 10 7 0 10 6 0 6 9 4 0 0 1 10 0 1 0 2 0 1 3 10 5 6 1 0 6 4 0 4 3 9 6 0 0 6 0 10 0 8 8 9 8 6 2 4 10 0 0 2 9 4 0 9 0 0 0 0 0 10 6 9 0 4 1 4 8 2 10 0
output:
3.133273702882513
result:
ok found '3.1332737', expected '3.1332740', error '0.0000001'
Test #14:
score: -100
Wrong Answer
time: 910ms
memory: 3920kb
input:
10 0 52 25 22 39 47 85 63 8 2 52 0 0 87 2 20 50 87 88 6 25 0 0 77 27 58 81 0 98 0 22 87 77 0 28 0 49 53 59 0 39 2 27 28 0 0 65 76 0 0 47 20 58 0 0 0 88 0 0 3 85 50 81 49 65 88 0 60 85 1 63 87 0 53 76 0 60 0 76 88 8 88 98 59 0 0 85 76 0 0 2 6 0 0 0 3 1 88 0 0
output:
28.971268592982288
result:
wrong answer 1st numbers differ - expected: '29.5429470', found: '28.9712686', error = '0.0193508'