QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#266615#7753. Energy Distributionqkm66666#WA 982ms4200kbC++172.1kb2023-11-26 15:54:372023-11-26 15:54:38

Judging History

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

  • [2024-10-31 10:22:30]
  • hack成功,自动添加数据
  • (/hack/1089)
  • [2023-11-26 15:54:38]
  • 评测
  • 测评结果:WA
  • 用时:982ms
  • 内存:4200kb
  • [2023-11-26 15:54:37]
  • 提交

answer

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<cstdio>
#include<cctype>
#include<vector>
#include<bitset>
#include<random>
#include<ctime>
#include<queue>
#include<cmath>
#include<list>
#include<map>
#include<set>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long,long long>
#define FF fflush(stdout)
#define inf 0x3f3f3f3f
#define endl "\n"
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
//char buf[1<<20],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
    int s=0,f=1;
    char x=getchar();
    while(!isdigit(x))f=(x=='-'?-1:1),x=getchar();
    while(isdigit(x))s=s*10+x-'0',x=getchar();
    return s*f;
}
const int p=1e9+7;
//ll ksm(int a,int b){ll ans=1,bs=a;while(b){if(b&1)ans=ans*bs%p;bs=bs*bs%p;b>>=1;}return ans;}
mt19937 rd(time(0));
#define reaD read
int w[13][13];
double e[13];
double ee[13];
int n;
double cal()
{
    double s=0;
    for(int i=1;i<=n;i++)
    s+=fabs(e[i]);
    for(int i=1;i<=n;i++)
    ee[i]=1.0*fabs(e[i])/s;
    double ans=0;
    for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
    ans+=w[i][j]*ee[i]*ee[j];
    // assert(ans<100000);
    return ans;
}
double SA()
{
    double t=1000;
    double dt=0.997;
    double ans=0;
    while(t>1e-5)
    {
        int x=rd()%n+1;
        double del=(rd()%2?-1:1)*1;
        e[x]+=del;
        double tmp=cal();
        if(tmp>=ans)
        {
            ans=tmp;
        }
        else if(exp((tmp-ans)/t)*RAND_MAX<=rand())
        {
            e[x]-=del;
        }
        if(t>1)t*=dt;
        else
        t*=dt;
    }
    return ans;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    w[i][j]=read();
    double ans=0;
    for(int i=1;i<=2000;i++)
    {
        for(int i=1;i<=n;i++)
        e[i]=1;
        ans=max(ans,SA());
    }
    printf("%.8lf",ans);
    // system("pause");
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 464ms
memory: 4100kb

input:

2
0 1
1 0

output:

0.25000000

result:

ok found '0.2500000', expected '0.2500000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 474ms
memory: 4112kb

input:

3
0 2 1
2 0 2
1 2 0

output:

0.57142857

result:

ok found '0.5714286', expected '0.5714290', error '0.0000004'

Test #3:

score: 0
Accepted
time: 471ms
memory: 4116kb

input:

3
0 1 2
1 0 1
2 1 0

output:

0.50000000

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #4:

score: 0
Accepted
time: 626ms
memory: 4180kb

input:

4
0 3 1 0
3 0 1 0
1 1 0 2
0 0 2 0

output:

0.75000000

result:

ok found '0.7500000', expected '0.7500000', error '0.0000000'

Test #5:

score: 0
Accepted
time: 727ms
memory: 4044kb

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.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #6:

score: 0
Accepted
time: 757ms
memory: 4116kb

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.85714286

result:

ok found '2.8571429', expected '2.8571430', error '0.0000000'

Test #7:

score: 0
Accepted
time: 802ms
memory: 4168kb

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.51157310

result:

ok found '12.5115731', expected '12.5115850', error '0.0000010'

Test #8:

score: 0
Accepted
time: 871ms
memory: 4132kb

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.00911593

result:

ok found '25.0091159', expected '25.0091180', error '0.0000001'

Test #9:

score: 0
Accepted
time: 937ms
memory: 4116kb

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:

119.00000000

result:

ok found '119.0000000', expected '119.0000000', error '0.0000000'

Test #10:

score: 0
Accepted
time: 982ms
memory: 4200kb

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.25000000

result:

ok found '240.2500000', expected '240.2500000', error '0.0000000'

Test #11:

score: -100
Wrong Answer
time: 982ms
memory: 4124kb

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.37146614

result:

wrong answer 1st numbers differ - expected: '327.3736590', found: '327.3714661', error = '0.0000067'