QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#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;
}
Details
Tip: Click on the bar to expand more detailed information
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'