QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#333403 | #7753. Energy Distribution | Yansuan_HCl | TL | 1ms | 4028kb | C++14 | 2.0kb | 2024-02-19 21:27:13 | 2024-02-19 21:27:14 |
Judging History
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