QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#333403#7753. Energy DistributionYansuan_HClTL 1ms4028kbC++142.0kb2024-02-19 21:27:132024-02-19 21:27:14

Judging History

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

  • [2024-10-31 10:22:30]
  • hack成功,自动添加数据
  • (/hack/1089)
  • [2024-02-19 21:27:14]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4028kb
  • [2024-02-19 21:27:13]
  • 提交

answer

#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline)) static
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;
using ll = long long;

#define IC isdigit(c)
#define GC c=getchar()
void rd(auto &x) { x = 0; char GC; bool f = 0;
	for (; !IC; GC) f |= c == '-';
	for (; IC; GC) x = x * 10 + c - 48;
	if (f) x = -x;
}
void rd(auto &x, auto &...y) { rd(x); rd(y...); }
#define meow(...) fprintf(stderr, __VA_ARGS__)
#define Assert(e) if (!(e)) { meow("AF@%d\n", __LINE__); exit(__LINE__); }

const int N = 12;
int n, w[N][N], s;

double e[N][N] {}; int var[N] {};
void gen() {
	ms(e, 0);
	U (i, 1, n) if ((s >> i) & 1) {
		U (j, i + 1, n) if ((s >> j) & 1)
			e[i][j] = w[i][j];
		U (j, 1, i) if ((s >> j) & 1)
			e[i][j] = w[j][i];
		if (s & 1)
			e[i][n + 1] = 1;
	}
	if (s & 1) {
		U (i, 1, n) if ((s >> i) & 1)
			e[n + 1][i] = 1;
		e[n + 1][n + 2] = 1;
	}
}
const double EPS = 1e-9;
bool equ(double x, double y) { return abs(x - y) < EPS; }
int gauss() {
	int rk = 0; ms(var, 0);
	U (i, 1, n + 1) {
		int j = rk + 1; for (; j <= n + 1 && equ(e[j][i], 0); ++j);
		if (j > n + 1) continue;
		++rk; var[rk] = i;
		U (k, 1, n + 2) swap(e[rk][k], e[j][k]);
		for (j = 1; j <= n + 1; ++j) if (j != rk) {
			double c = e[j][i] / e[rk][i];
			U (k, 1, n + 2)
				e[j][k] -= e[rk][k] * c;
		}
	}
	return rk;
}

int main() {

	rd(n);
	U (i, 1, n) U (j, 1, n) rd(w[i][j]);
	double ans = -1;
	for (s = 0; s < (1 << (n + 1)); ++s) {
		gen();
		int rk = gauss();
		if (rk != __builtin_popcount(s))
			continue;
		double res[N] {}, cur = 0;
		U (i, 1, n + 1) if (var[i]) {
			if (equ(e[i][var[i]], 0) && !equ(e[i][n + 2], 0))
				goto CONT;
			if (var[i] <= n) {
				res[var[i]] = e[i][n + 2] / e[i][var[i]];
				if (res[var[i]] < 0)
					goto CONT;
			}
		}
		U (i, 1, n) U (j, i + 1, n)
			cur += res[i] * res[j] * w[i][j];
		ans = max(ans, cur);
CONT:;
	}
	printf("%.6lf\n", ans);
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3872kb

input:

2
0 1
1 0

output:

0.250000

result:

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

Test #2:

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

input:

3
0 2 1
2 0 2
1 2 0

output:

0.571429

result:

ok found '0.5714290', expected '0.5714290', error '0.0000000'

Test #3:

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

input:

3
0 1 2
1 0 1
2 1 0

output:

0.500000

result:

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

Test #4:

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

input:

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

output:

0.750000

result:

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

Test #5:

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

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

result:

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

Test #6:

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

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

result:

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

Test #7:

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

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

result:

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

Test #8:

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

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

result:

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

Test #9:

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

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

result:

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

Test #10:

score: -100
Time Limit Exceeded

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:


result: