QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#268292#7753. Energy DistributionSATSKYWA 1ms3600kbC++202.3kb2023-11-28 15:18:302023-11-28 15:18:30

Judging History

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

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

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'