QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #1088 | #691084 | #7753. Energy Distribution | sunnygreen | sunnygreen | Failed. | 2024-10-31 10:03:30 | 2024-10-31 10:03:31 |
详细
Extra Test:
Accepted
time: 1ms
memory: 3904kb
input:
10 0 783 679 125 653 494 535 927 685 209 783 0 49 120 337 102 919 902 737 28 679 49 0 111 552 568 377 381 174 638 125 120 111 0 147 29 633 806 51 337 653 337 552 147 0 447 353 683 78 795 494 102 568 29 447 0 960 949 941 649 535 919 377 633 353 960 0 874 282 241 927 902 381 806 683 949 874 0 793 463 ...
output:
314.039651386
result:
ok found '314.0396514', expected '314.0396540', error '0.0000000'
| 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;
}