QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#268176#7753. Energy DistributionFISHER_WA 569ms3860kbC++141.6kb2023-11-28 12:20:252023-11-28 12:20:26

Judging History

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

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

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10;
int w[maxn + 5][maxn + 5];
double e[maxn + 5];
int et[maxn + 5];
double find_fraction(double x) {
	double minDiff = x + 1;
	int a = 0, b = 1;
	for (int i = 1; i <= 1000; i++) {
		int j = round(i * x);
		double diff = abs(x - (double)j / i);
		if (diff < minDiff) {
			minDiff = diff;
			a = j;
			b = i;
		}
	}
 
	return (double)a / b;
}
int main() {
	srand(time(0));
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) scanf("%d", &w[i][j]);
	double ans = 0;
	int T2 = 10000;
	while (T2--) {
		long long es = 0;
		for (int i = 1; i <= n; i++) es += et[i] = rand();
		for (int i = 1; i <= n; i++) e[i] = 1. * et[i] / es;
		int T = 1000;
		while (T--) {
			int x = rand() % n + 1, y = rand() % n + 1;
			while (x == y) x = rand() % n + 1, y = rand() % n + 1;
			if (x > y) swap(x, y);
			double s = e[x] + e[y];
			double c1 = 0, c2 = 0;
			for (int i = x + 1; i <= n; i++)
				if (i != y) c1 += e[i] * w[x][i];
			for (int i = y + 1; i <= n; i++) c1 -= e[i] * w[y][i];
			for (int i = 1; i < x; i++) c1 += e[i] * w[i][x];
			for (int i = 1; i < y; i++)
				if (i != x) c1 -= e[i] * w[i][y];
			c2 -= w[x][y], c1 += s * w[x][y];
			if (abs(c2) == 0) continue;
			e[x] = max(-c1 / (2 * c2), 0.);
			e[x] = min(e[x], s);
			e[y] = s - e[x];
		}
		for (int i = 1; i <= n; i++) e[i] = find_fraction(e[i]);
		double sum = 0;
		for (int i = 1; i <= n; i++)
			for (int j = i + 1; j <= n; j++) sum += e[i] * e[j] * w[i][j];
		ans = max(ans, sum);
	}
	printf("%.7lf", ans);
}

詳細信息

Test #1:

score: 100
Accepted
time: 518ms
memory: 3860kb

input:

2
0 1
1 0

output:

0.2500000

result:

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

Test #2:

score: 0
Accepted
time: 510ms
memory: 3628kb

input:

3
0 2 1
2 0 2
1 2 0

output:

0.5714286

result:

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

Test #3:

score: 0
Accepted
time: 511ms
memory: 3648kb

input:

3
0 1 2
1 0 1
2 1 0

output:

0.5000000

result:

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

Test #4:

score: 0
Accepted
time: 542ms
memory: 3688kb

input:

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

output:

0.7500000

result:

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

Test #5:

score: -100
Wrong Answer
time: 569ms
memory: 3844kb

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.0008926

result:

wrong answer 1st numbers differ - expected: '1.0000000', found: '1.0008926', error = '0.0008926'