QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#266606 | #7753. Energy Distribution | qkm66666# | WA | 789ms | 4188kb | C++17 | 2.1kb | 2023-11-26 15:50:44 | 2023-11-26 15:50:44 |
Judging History
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)*(rd()%10);
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: 488ms
memory: 3984kb
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: 518ms
memory: 3952kb
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: 514ms
memory: 4136kb
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: 662ms
memory: 4188kb
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: 757ms
memory: 4188kb
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: -100
Wrong Answer
time: 789ms
memory: 4132kb
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.81250000
result:
wrong answer 1st numbers differ - expected: '2.8571430', found: '2.8125000', error = '0.0156250'