QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #1089 | #691084 | #7753. Energy Distribution | sunnygreen | sunnygreen | Success! | 2024-10-31 10:22:17 | 2024-10-31 10:22:18 |
詳細信息
Extra Test:
Wrong Answer
time: 1ms
memory: 3900kb
input:
8 0 671 740 179 404 416 868 39 671 0 573 168 615 32 26 589 740 573 0 385 722 984 568 114 179 168 385 0 607 782 953 669 404 615 722 607 0 5 553 51 416 32 984 782 5 0 319 183 868 26 568 953 553 319 0 91 39 589 114 669 51 183 91 0
output:
253.316155965
result:
wrong answer 1st numbers differ - expected: '253.3176620', found: '253.3161560', error = '0.0000059'
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #691084 | #7753. Energy Distribution | sunnygreen | WA | 1ms | 3952kb | C++14 | 2.2kb | 2024-10-31 09:44:32 | 2024-10-31 10:31:22 |
answer
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define fi first
#define se second
#define mk make_pair
#define eb emplace_back
#define rep(i,l,r) for(int i=(l); i<=(r); ++i)
#define rep_(i,l,r) for(int i=(l); i>=(r); --i)
typedef long long lr;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
constexpr int mod1=998244353,mod2=1e9+7;
constexpr db pi=3.141592653589793,eps=1e-9;
constexpr int inf32=0x3f3f3f3f,Inf32=0xc0c0c0c0;
constexpr lr inf64=0x3f3f3f3f3f3f3f3f,Inf64=0xc0c0c0c0c0c0c0c0;
template<typename T>il T Max(T x,T y) { return (x>y)? x:y; }
template<typename T>il T Min(T x,T y) { return (x<y)? x:y; }
template<typename T>il T gcd(T x,T y) { return (!y)? x:gcd(y,x%y); }
template<typename T>il T Abs(T x) { return (x>0)? x:(-x); }
template<typename T>il T Rnd(T l,T r,mt19937_64 &eng)
{
uniform_int_distribution<T> uid(l,r);
return uid(eng);
}
mt19937_64 eng(chrono::high_resolution_clock::now().time_since_epoch().count());
constexpr int N=15;
int n,val[N],w[N][N];
db p[N];
il void chk(int x,int y)
{
db X=0,Y=0;
rep(i,1,n)
if(i!=x&&i!=y)
X+=p[i]*w[x][i],Y+=p[i]*w[y][i];
if(!w[x][y])
{
(X>Y)? (p[x]+=p[y],p[y]=0):(p[y]+=p[x],p[x]=0);
return;
}
db xx=0.5*(X-Y+w[x][y]*(p[x]+p[y]))/w[x][y],yy=0.5*(Y-X+w[x][y]*(p[x]+p[y]))/w[x][y];
if(xx<0)
yy+=xx,xx=0;
if(yy<0)
xx+=yy,yy=0;
p[x]=xx,p[y]=yy;
}
il void Solve()
{
cin>>n;
rep(i,1,n)
rep(j,1,n)
cin>>w[i][j];
db bp=0;
int Q=30;
while(Q--)
{
int sum=0;
rep(i,1,n)
val[i]=Rnd(20210416,80000000,eng),sum+=val[i];
rep(i,1,n)
p[i]=1.0*val[i]/sum;
rep(i,1,300)
{
int x=Rnd(1,n,eng),y=Rnd(1,n,eng);
while(x==y)
x=Rnd(1,n,eng),y=Rnd(1,n,eng);
chk(x,y);
}
db ans=0;
rep(i,1,n)
rep(j,i+1,n)
ans+=p[i]*p[j]*w[i][j];
bp=Max(bp,ans);
}
cout<<setiosflags(ios::fixed)<<setprecision(9)<<bp<<'\n';
}
int main()
{
#ifdef LOCAL
string fpre="test",isuf="in",osuf="out";
assert(freopen((fpre+"."+isuf).c_str(),"r",stdin));
assert(freopen((fpre+"."+osuf).c_str(),"w",stdout));
#endif
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
while(T--)
Solve();
return 0;
}