QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #638671 | #7753. Energy Distribution | wyhao | TL | 496ms | 4268kb | C++14 | 1.5kb | 2024-10-13 16:35:12 | 2024-10-13 16:35:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n;
int w[N][N];
double x[N];
double E(){
double ans = 0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
ans += x[i]*x[j]*w[i][j];
}
}
return -ans;
}
int main(){
// freopen("ex.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) scanf("%d",&w[i][j]);
}
int S=0;
// for(int i=1;i<=n;i++) x[i]=rand(),S+=x[i];
// for(int i=1;i<=n;i++) x[i]=x[i]/S;
double ANS=0;
for(int K=1;K<(1<<n);K++){
int tt=0;
for(int i=1;i<=n;i++){
if((K>>(i-1))&1) tt++;
}
for(int i=1;i<=n;i++){
if((K>>(i-1))&1) x[i]=1.0/tt;
else x[i]=0;
}
double ans = E(),T=ans,a=0.99;
for(int I=1;I<=100000;I++){
int u=rand()%n+1,v=rand()%n+1;
while(u==v) v=rand()%n+1;
int p=rand()%100001;
double dtx = x[u]*p/100000;
x[u]-=dtx;x[v]+=dtx;
double ansk=E();
if(ansk>=ans){
double pp=(1ll*rand()*rand()%10000)/10000.0;
if(exp((ans-ansk)/T)>pp){
x[u]+=dtx;
x[v]-=dtx;
}else ans=ansk;
}else ans = ansk;
T*=a;
// if(I<10)printf("%.9lf\n",-ans);
}
ANS=max(ANS,-ans);
}
printf("%.9lf",ANS);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 22ms
memory: 4264kb
input:
2 0 1 1 0
output:
0.250000000
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 48ms
memory: 4204kb
input:
3 0 2 1 2 0 2 1 2 0
output:
0.571428571
result:
ok found '0.5714286', expected '0.5714290', error '0.0000004'
Test #3:
score: 0
Accepted
time: 48ms
memory: 4152kb
input:
3 0 1 2 1 0 1 2 1 0
output:
0.500000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 103ms
memory: 4268kb
input:
4 0 3 1 0 3 0 1 0 1 1 0 2 0 0 2 0
output:
0.750000000
result:
ok found '0.7500000', expected '0.7500000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 223ms
memory: 4160kb
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.000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 496ms
memory: 4216kb
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.857142856
result:
ok found '2.8571429', expected '2.8571430', error '0.0000001'
Test #7:
score: -100
Time Limit Exceeded
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.511584801