QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#261167#7753. Energy DistributionLoging#WA 1ms3756kbC++202.8kb2023-11-22 18:31:302023-11-22 18:31:30

Judging History

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

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

answer

#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-9;

struct Matrix {
	int n , m;
	double v[10 + 5][10 + 5];
	Matrix(int _n) : n(_n) , m(_n + 1) {
		for (int i = 0 ; i < n ; i++) {
			for (int j = 0 ; j < m ; j++) {
				v[i][j] = 0;
			}
		}
	}
	void print() {
		for (int i = 0 ; i < n ; i++) {
			for (int j = 0 ; j < m ; j++) {
				cout << v[i][j] << ' ';
			}
			cout << endl;
		}
		cout << endl;
	}
	vector<double> solve(int &f) {
		int r = 0;
		for (int i = 0 ; i < n ; i++) {
//			cout << i << endl;
			for (int j = r + 1 ; j < n ; j++) {
				if (fabs(v[j][i]) > eps) {
					swap(v[j] , v[r]);
				}
			}
			if (fabs(v[r][i]) <= eps) continue;
//			cout << "YES" << i << endl;
//			print();
			
			double d = v[r][i];
			for (int j = i ; j < m ; j++) v[r][j] /= d;
			for (int j = r + 1 ; j < n ; j++) {
				double coef = v[j][i];
				for (int k = 0 ; k < m ; k++) {
					v[j][k] -= v[r][k] * coef;
				}
			}
			r++;
//			print();
		}
		
//		cout << "YES" << endl;
		vector<double> ans(n);
		for (int i = r - 1 ; i >= 0 ; i--) {
//			cout << i << endl;
			
//			cout << "YES" << i << endl;
			int p;
			for (int j = 0 ; j < m ; j++) {
				if (fabs(v[i][j]) > eps) {
					p = j;
					break;
				}
			}
//			cout << p << endl;
//			print();
			for (int j = i - 1 ; j >= 0 ; j--) {
				double coef = v[j][p];
				for (int k = 0 ; k < m ; k++) {
					v[j][k] -= coef * v[i][k];
				}
			}
			ans[p] = v[i][m - 1];
//			cout << p << ' ' << ans[p] << endl;
		}
//		cout << "YES" << endl;
		for (int i = r ; i < n ; i++) {
//			cout << i << endl;
			int flag = fabs(v[i][m - 1]) > eps;
			for (int j = 0 ; j < m - 1 ; j++) {
				flag &= fabs(v[i][j]) <= eps;
			}
			if (flag == 1) f = 0;
		}
//		cout << "F" << f << endl;
		return ans;
	}
	
};

int main() {
	cin.tie(nullptr)->sync_with_stdio(0);
	
	int n;
	cin >> n;
	
	vector<vector<int>> a(n , vector<int>(n));
	for (int i = 0 ; i < n ; i++) {
		for (int j = 0 ; j < n ; j++) {
			cin >> a[i][j];
		}
	}
	
	double ans = 0;
	for (int s = 0 ; s < (1 << n) ; s++) {
//		cout << "cur:" << s << endl;
		Matrix mat(n + 1);
		for (int i = 0 ; i < n ; i++) {
			if (s >> i & 1) {
				for (int j = 0 ; j < n ; j++) {
					if (s >> j & 1) {
						if (i != j) mat.v[i][j] = a[i][j];
					}
				}
				mat.v[i][n] = -1;
				mat.v[n][i] = 1;
			}
		}
		mat.v[n][n + 1] = 1;
		int flag = 1;
		
//		mat.print();
		auto e = mat.solve(flag);
//		for (int i = 0 ; i < n ; i++) {
//			cout << e[i] << ' ';
//		}
//		cout << endl;
		if (flag == 1) {
			double ret = 0;
			for (int i = 0 ; i < n ; i++) {
				for (int j = i + 1 ; j < n ; j++) {
					ret += e[i] * e[j] * a[i][j];
				}
			}
			ans = max(ans , ret);
		}
	}
	cout << setprecision(12) << fixed;
	cout << ans << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3588kb

input:

2
0 1
1 0

output:

0.250000000000

result:

ok found '0.2500000', expected '0.2500000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

3
0 2 1
2 0 2
1 2 0

output:

0.571428571429

result:

ok found '0.5714286', expected '0.5714290', error '0.0000004'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

3
0 1 2
1 0 1
2 1 0

output:

0.500000000000

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3508kb

input:

4
0 3 1 0
3 0 1 0
1 1 0 2
0 0 2 0

output:

1.000000000000

result:

wrong answer 1st numbers differ - expected: '0.7500000', found: '1.0000000', error = '0.2500000'