QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#268292 | #7753. Energy Distribution | SATSKY | WA | 1ms | 3600kb | C++20 | 2.3kb | 2023-11-28 15:18:30 | 2023-11-28 15:18:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;const double eps=1e-10;using ll=long long;const int M=998244353;
struct Mat
{
int n,m;vector<vector<double>>mat;vector<int>sol;Mat(int _n,int _m) { ini(_n,_m); }
void ini(int _n,int _m) { n=_n,m=_m,mat.resize(n,vector<double>(m,0)); }
int Gauss()
{//0:none/1:only sol/2:multi sol
int pt=0;for(int c=0;c<n;c++)
{
int t=pt;for(int i=pt;i<n;i++)if(abs(mat[i][c])>abs(mat[t][c]))t=i;
if(abs(mat[t][c])<eps)continue;swap(mat[t],mat[pt]);for(int i=m-1;i>=c;i--)mat[pt][i]/=mat[pt][c];
for(int i=0;i<n;i++)if(pt!=i&&abs(mat[i][c])>eps)for(int j=m-1;j>=c;j--)mat[i][j]-=mat[pt][j]*mat[i][c];pt++;
//outp();
}
for(int i=pt+1;i<n;i++)if(abs(mat[i][m-1])>eps)
{
bool jud=0;for(int j=0;j<m-1;j++)jud|=(abs(mat[i][j])>eps);if(!jud)return 0;
}
return 2-bool(pt==n-1);
}
void outp(){for(int i=0;i<n;i++)for(int j=0;j<m;j++)cout<<mat[i][j]<<" \n"[j==m-1];cout<<"%%%\n"; }
};
struct S
{
int n;
void solve()
{
cin>>n;vector<vector<int>>a(n,vector<int>(n));for(auto &k:a)for(auto&kk:k)cin>>kk;int B=(1<<n);double mx=0;
for(int k=1;k<B;k++)
{
vector<int>arr;for(int i=0;i<n;i++)if(k&(1<<i))arr.push_back(i);int siz=arr.size();
Mat A(siz,siz+1);
for(int i=0;i<siz;A.mat[i][siz]=1,i++)for(int j=0;j<siz;j++)
if(i!=j)A.mat[i][j]=(i<j)?a[arr[i]][arr[j]]:a[arr[j]][arr[i]];
//cout<<'\n';
//cout<<(bitset<4>)k<<":\n";
//A.outp();
int x=A.Gauss();//cout<<x<<"!\n";
//cout<<dec<<k<<'\n';
//for(int b2=B;b2>=2;b2>>=1)cout<<(k%b2>=b2/2);
//A.outp();
if(x!=1)continue;
vector<double>res(siz,0);double sum=0;
for(int i=0;i<siz;i++)for(int j=0;j<siz;j++)if(abs(A.mat[i][j])>eps) { res[j]=A.mat[i][siz],sum+=res[j];break; }
//for(auto k:res)cout<<k<<'_';cout<<'\n';
if(abs(sum)<eps)continue;for(auto &k:res)k/=sum;sum=0;
for(int i=0;i<siz;i++)for(int j=i+1;j<siz;j++)sum+=res[i]*res[j]*a[arr[i]][arr[j]];
mx=max(mx,sum);//cout<<"SUM:"<<sum<<'\n';
}
cout<<mx<<'\n';
}
};
int main()
{
//int x=25;
//cout<<hex<<x<<' '<<dec<<x<<' '<<oct<<x<<' '<<bin<<x<<'\n';
//16/10/8/2
//return 0;
//freopen("1.in","r",stdin);
cout<<fixed<<setprecision(12);
ios::sync_with_stdio(0);cin.tie(0);
int t=1;/*cin>>t;*/
while(t--) { S SS;SS.solve(); }
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3600kb
input:
2 0 1 1 0
output:
0.000000000000
result:
wrong answer 1st numbers differ - expected: '0.2500000', found: '0.0000000', error = '0.2500000'