QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#361364 | #3400. 重建 | Pengzt | 100 ✓ | 1ms | 4004kb | C++14 | 1.8kb | 2024-03-23 09:08:20 | 2024-03-23 09:08:20 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define pb emplace_back
using namespace std;
#define db double
const db eps = 1e-7;
int n;
db a[110][110], ans = 1;
double det(int n) {
// cout << fixed << setprecision(7);
// cout << "Matrix A: \n";
// for(int i = 1; i <= n; ++i, cout << "\n")
// for(int j = 1; j <= n; ++j)
// cout << a[i][j] << " ";
int coef = 0;
db ret = 1;
for(int i = 1; i <= n; ++i) {
int p = i;
for(int j = i; j <= n; ++j)
if(fabs(a[j][i]) > fabs(a[p][i]))
p = j;
if(i ^ p)
swap(a[i], a[p]), coef ^= 1;
if(fabs(a[i][i]) < eps)
cout << "?\n", exit(0);
for(int j = i + 1; j <= n; ++j) {
db t = a[j][i] / a[i][i];
for(int k = i; k <= n; ++k)
a[j][k] -= t * a[i][k];
}
ret *= a[i][i];
}
return !coef ? ret : -ret;
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j) {
cin >> a[i][j];
if(fabs(1 - a[i][j]) < eps)
a[i][j] = 1 - eps;
if(i < j)
ans *= (1 - a[i][j]);
a[i][j] = a[i][j] / (1 - a[i][j]);
}
for(int i = 1; i <= n; ++i) {
a[i][i] = 0;
for(int j = 1; j <= n; ++j)
if(i ^ j)
a[i][i] += a[i][j], a[i][j] *= -1;
}
ans *= det(n - 1);
cout << ans << "\n";
return 0;
}
/*
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.13884
*/
詳細信息
Test #1:
score: 10
Accepted
time: 1ms
memory: 4004kb
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.999999
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #2:
score: 10
Accepted
time: 0ms
memory: 3928kb
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: 3932kb
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: 3928kb
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.00607841
result:
ok found '0.00608', expected '0.00608', error '0.00000'
Test #5:
score: 10
Accepted
time: 0ms
memory: 3892kb
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.000137119
result:
ok found '0.00014', expected '0.00014', error '0.00000'
Test #6:
score: 10
Accepted
time: 0ms
memory: 3948kb
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.000100158
result:
ok found '0.00010', expected '0.00010', error '0.00000'
Test #7:
score: 10
Accepted
time: 0ms
memory: 3932kb
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.000146056
result:
ok found '0.00015', expected '0.00015', error '0.00000'
Test #8:
score: 10
Accepted
time: 1ms
memory: 3976kb
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.000238191
result:
ok found '0.00024', expected '0.00024', error '0.00000'
Test #9:
score: 10
Accepted
time: 1ms
memory: 3920kb
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.000333006
result:
ok found '0.00033', expected '0.00033', error '0.00000'
Test #10:
score: 10
Accepted
time: 1ms
memory: 3780kb
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.000108033
result:
ok found '0.00011', expected '0.00011', error '0.00000'