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