QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#261185#7753. Energy DistributionLoging#WA 1ms3768kbC++203.0kb2023-11-22 18:42:042023-11-22 18:42:05

Judging History

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

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

answer

#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-12;

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];
		}
	}
	for (int i = 0 ; i < n ; i++) {
		a[i][i] = 0;
		for (int j = i + 1 ; j < n ; j++) {
			a[j][i] = 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] << ' ';
			if (e[i] < -eps) flag = 0;
		}
//		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: 0ms
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: 3764kb

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: 3752kb

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: 0
Accepted
time: 1ms
memory: 3596kb

input:

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

output:

0.750000000000

result:

ok found '0.7500000', expected '0.7500000', error '0.0000000'

Test #5:

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

input:

5
0 0 0 4 4
0 0 2 0 4
0 2 0 2 0
4 0 2 0 0
4 4 0 0 0

output:

1.000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

6
0 9 5 5 10 6
9 0 0 0 0 1
5 0 0 0 3 0
5 0 0 0 10 5
10 0 3 10 0 0
6 1 0 5 0 0

output:

2.857142857143

result:

ok found '2.8571429', expected '2.8571430', error '0.0000000'

Test #7:

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

input:

7
0 0 0 0 50 10 45
0 0 0 0 0 3 1
0 0 0 0 0 4 16
0 0 0 0 44 0 0
50 0 0 44 0 37 6
10 3 4 0 37 0 2
45 1 16 0 6 2 0

output:

12.511584800741

result:

ok found '12.5115848', expected '12.5115850', error '0.0000000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

8
0 0 56 0 0 58 16 0
0 0 37 20 0 82 0 0
56 37 0 0 98 0 83 0
0 20 0 0 0 0 100 0
0 0 98 0 0 62 29 0
58 82 0 0 62 0 43 0
16 0 83 100 29 43 0 4
0 0 0 0 0 0 4 0

output:

25.009117896522

result:

ok found '25.0091179', expected '25.0091180', error '0.0000000'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3768kb

input:

9
0 0 0 135 0 0 0 448 476
0 0 0 0 0 0 208 17 0
0 0 0 467 1 0 0 0 134
135 0 467 0 0 0 92 369 207
0 0 1 0 0 176 0 235 0
0 0 0 0 176 0 65 363 413
0 208 0 92 0 65 0 0 0
448 17 0 369 235 363 0 0 0
476 0 134 207 0 413 0 0 0

output:

119.000000000000

result:

ok found '119.0000000', expected '119.0000000', error '0.0000000'

Test #10:

score: -100
Wrong Answer
time: 1ms
memory: 3620kb

input:

10
0 0 0 289 0 397 0 0 140 155
0 0 28 101 35 614 0 0 545 300
0 28 0 0 329 702 0 242 0 298
289 101 0 0 0 0 0 0 720 0
0 35 329 0 0 0 0 38 0 0
397 614 702 0 0 0 229 0 0 0
0 0 0 0 0 229 0 317 0 0
0 0 242 0 38 0 317 0 961 309
140 545 0 720 0 0 0 961 0 92
155 300 298 0 0 0 0 309 92 0

output:

334149.304306241567

result:

wrong answer 1st numbers differ - expected: '240.2500000', found: '334149.3043062', error = '1389.8399763'