QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#361364#3400. 重建Pengzt100 ✓1ms4004kbC++141.8kb2024-03-23 09:08:202024-03-23 09:08:20

Judging History

This is the latest submission verdict.

  • [2024-03-23 09:08:20]
  • Judged
  • Verdict: 100
  • Time: 1ms
  • Memory: 4004kb
  • [2024-03-23 09:08:20]
  • Submitted

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'