QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#468627 | #3400. 重建 | little_sun | 100 ✓ | 1ms | 4048kb | C++14 | 1.7kb | 2024-07-08 21:53:45 | 2024-07-08 21:53:45 |
Judging History
answer
#include <bits/stdc++.h>
#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)
#define meow(cat...) fprintf(stderr, cat)
const double eps = 1e-7;
int n;
double a[100][100], f[100][100];
double d[100][100], g[100][100];
int check(double x)
{
if(x > eps) return 1;
else if(x < -eps) return -1;
else return 0;
}
double solve()
{
double res = 1.0;
// for(int i = 1; i < n; i++)
// for(int j = 1; j < n; j++)
// printf("%lf%c", a[i][j], " \n"[j == n - 1]);
for(int i = 1; i < n; i++)
for(int j = i + 1; j < n; j++)
{
while(check(a[i][i]))
{
double rate = a[j][i] / a[i][i];
for(int k = i; k < n; k++)
a[j][k] -= rate * a[i][k];
std::swap(a[i], a[j]), res = -res;
}
std::swap(a[i], a[j]), res = -res;
}
for(int i = 1; i < n; i++)
res = res * a[i][i];
return res;
}
signed main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
scanf("%lf", &f[i][j]);
if(check(f[i][j] - 1.0) == 0) f[i][j] = 1.0 - eps;
else if(check(f[i][j]) == 0) f[i][j] = eps;
double r = f[i][j] / (1.0 - f[i][j]);
if(i <= j) continue;
g[i][j] = g[j][i] = r, d[i][i] += r, d[j][j] += r;
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
a[i][j] = d[i][j] - g[i][j];
double ans = solve();
for(int i = 1; i <= n; i++)
for(int j = i + 1; j <= n; j++)
ans *= (1.0 - f[i][j]);
printf("%lf\n", ans);
return 0;
}
详细
Test #1:
score: 10
Accepted
time: 0ms
memory: 3892kb
input:
10 0.00 0.00 0.00 0.00 1.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 1.00 0.00 1.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 1.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 1.00 0.00 0.00 1.00 1.00 1.00 0.00 0.00 0.00 0.00 0.00 1.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 1.00 0....
output:
0.999996
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #2:
score: 10
Accepted
time: 0ms
memory: 3936kb
input:
8 0.0 1.0 0.25 0.875 0.0 0.25 1.0 0.25 1.0 0.0 0.0 0.25 0.0 0.0 0.0 0.25 0.25 0.0 0.0 0.0 0.0 0.875 0.125 0.0 0.875 0.25 0.0 0.0 0.0 0.125 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.0 0.25 0.0 0.875 0.125 0.0 0.0 1.0 1.0 1.0 0.0 0.125 0.0 1.0 1.0 0.0 0.125 0.25 0.25 0.0 0.0 0.0 1.0 0.125 0.0 0.0 0.0
output:
0.138839
result:
ok found '0.13884', expected '0.13884', error '0.00000'
Test #3:
score: 10
Accepted
time: 0ms
memory: 3976kb
input:
7 0.0 1.0 0.0 1.0 0.0 1.0 0.0 1.0 0.0 0.375 0.25 0.0 0.0 1.0 0.0 0.375 0.0 0.25 0.0 1.0 0.125 1.0 0.25 0.25 0.0 0.75 0.125 0.0 0.0 0.0 0.0 0.75 0.0 0.0 0.0 1.0 0.0 1.0 0.125 0.0 0.0 0.0 0.0 1.0 0.125 0.0 0.0 0.0 0.0 0.0 0.0
output:
0.201874
result:
ok found '0.20187', expected '0.20187', error '0.00000'
Test #4:
score: 10
Accepted
time: 0ms
memory: 3888kb
input:
10 0.00 0.02 1.00 0.03 0.03 0.80 0.03 0.03 0.80 0.90 0.02 0.00 0.02 0.02 0.04 0.90 0.04 0.01 0.04 0.02 1.00 0.02 0.00 0.02 0.80 0.35 0.80 1.00 0.02 0.01 0.03 0.02 0.02 0.00 0.04 1.00 0.01 0.90 0.02 0.01 0.03 0.04 0.80 0.04 0.00 0.02 0.90 0.03 1.00 0.35 0.80 0.90 0.35 1.00 0.02 0.00 0.03 0.02 0.03 0....
output:
0.006078
result:
ok found '0.00608', expected '0.00608', error '0.00000'
Test #5:
score: 10
Accepted
time: 0ms
memory: 3940kb
input:
12 0.00 0.02 0.30 0.20 0.30 0.20 0.21 0.21 0.20 0.21 0.30 0.65 0.02 0.00 0.20 0.60 1.00 0.20 0.20 0.21 0.20 0.30 0.02 0.30 0.30 0.20 0.00 0.20 0.02 0.60 0.20 0.02 0.65 0.20 0.21 0.02 0.20 0.60 0.20 0.00 0.20 0.20 0.20 0.30 0.65 0.60 0.02 0.21 0.30 1.00 0.02 0.20 0.00 0.21 0.30 1.00 0.20 0.60 0.21 0....
output:
0.000137
result:
ok found '0.00014', expected '0.00014', error '0.00000'
Test #6:
score: 10
Accepted
time: 0ms
memory: 4000kb
input:
16 0.0 0.25 0.0 0.0 1.0 0.75 0.0 0.0 1.0 0.125 0.0 0.25 0.0 0.0 0.25 0.0 0.25 0.0 0.0 0.0 0.0 0.125 0.0 0.0 0.0 0.125 0.875 0.0 0.0 0.0 1.0 0.0 0.0 0.0 0.0 0.0 0.25 0.125 0.375 1.0 0.0 0.375 0.25 0.0 1.0 0.25 0.0 0.125 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.25 0.0 1.0 0.0 0.0 0.0 0.0 0.0 1.0 0.0 0.25 0.0...
output:
0.000100
result:
ok found '0.00010', expected '0.00010', error '0.00000'
Test #7:
score: 10
Accepted
time: 0ms
memory: 3956kb
input:
16 0.00 0.07 0.07 0.10 0.18 0.10 0.02 0.10 0.15 0.10 0.18 0.15 1.00 0.02 0.18 0.15 0.07 0.00 0.87 0.65 0.07 0.07 0.10 0.02 0.07 0.15 0.02 0.15 0.10 0.18 0.90 0.02 0.07 0.87 0.00 0.10 0.07 0.07 0.15 0.07 0.02 0.10 0.02 0.65 0.07 0.65 0.02 0.07 0.10 0.65 0.10 0.00 0.10 0.02 0.10 0.07 0.15 0.02 0.18 0....
output:
0.000146
result:
ok found '0.00015', expected '0.00015', error '0.00000'
Test #8:
score: 10
Accepted
time: 1ms
memory: 4048kb
input:
45 0.00 0.00 0.00 0.00 0.00 0.00 0.02 0.01 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.02 0.00 0.00 0.00 0.00 0.00 0.02 0.00 0.00 0.00 0.00 0.00 0.98 0.00 0.01 0.00 0.00 0.00 0.00 0.00 0.02 0.02 0.00 0.00 0.00 0.01 0.02 0.00 0.02 0.90 0.00 0.00 0.00 0.00 0.00 0.01 0.01 0.01 0.01 0.01 0.02 0.00 0.00 0.00 0....
output:
0.000238
result:
ok found '0.00024', expected '0.00024', error '0.00000'
Test #9:
score: 10
Accepted
time: 1ms
memory: 4036kb
input:
40 0.00 0.00 0.02 0.01 0.00 0.00 0.02 0.00 0.00 0.00 0.02 0.01 0.00 0.01 0.00 0.95 0.00 0.02 0.01 0.00 0.90 0.01 0.01 0.02 0.00 0.00 0.00 0.00 0.00 0.01 0.00 0.00 0.00 0.01 0.01 0.02 0.00 0.00 0.02 0.00 0.00 0.00 0.00 0.00 0.00 0.01 0.00 0.01 0.00 0.00 0.00 0.00 0.02 0.00 0.01 0.01 0.00 0.02 0.00 0....
output:
0.000333
result:
ok found '0.00033', expected '0.00033', error '0.00000'
Test #10:
score: 10
Accepted
time: 1ms
memory: 3936kb
input:
45 0.00 0.90 0.00 0.02 0.00 0.00 0.00 0.02 0.01 0.90 0.96 0.00 0.00 0.00 0.00 0.00 0.02 0.01 0.00 0.00 0.02 0.00 0.01 0.00 0.02 0.00 0.00 0.00 0.00 0.00 0.01 0.00 0.00 0.00 0.90 0.00 0.00 0.00 0.98 0.00 0.01 0.00 0.02 0.00 0.00 0.90 0.00 0.00 0.00 0.00 0.00 0.02 0.00 0.00 0.00 0.01 0.02 0.00 0.00 0....
output:
0.000108
result:
ok found '0.00011', expected '0.00011', error '0.00000'