QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#60519#3400. 重建Steven_lzx100 ✓3ms3756kbC++17992b2022-11-05 10:51:012022-11-05 10:51:03

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-05 10:51:03]
  • 评测
  • 测评结果:100
  • 用时:3ms
  • 内存:3756kb
  • [2022-11-05 10:51:01]
  • 提交

answer

/*
 * Title: P3317 [SDOI2014]重建
 * Source: 洛谷
 * URL: https://www.luogu.com.cn/problem/P3317
 * Author: Steven_lzx
 * Command: -std=c++17 -Wall -fno-ms-extensions
 * Date: 2022.11.5
 */
#include <bits/stdc++.h>
using namespace std;
const double EPS=1e-10;
int n;
double l[55][55];
int main()
{
    double ans=1,x,temp;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%lf",&x);
            x+=EPS;
            if(i!=j)
            {
                l[i][j]=-x/(1-x);
                l[i][i]+=x/(1-x);
                if(i<j)
                    ans*=(1-x);
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            temp=l[j][i]/l[i][i];
            for(int k=i;k<=n;k++)
            {
                l[j][k]-=l[i][k]*temp;
            }
        }
        ans*=l[i][i];
    }
    printf("%.4lf\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 3ms
memory: 3744kb

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:

1.0000

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #2:

score: 10
Accepted
time: 2ms
memory: 3592kb

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.1388

result:

ok found '0.13880', expected '0.13884', error '0.00004'

Test #3:

score: 10
Accepted
time: 3ms
memory: 3560kb

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.2019

result:

ok found '0.20190', expected '0.20187', error '0.00003'

Test #4:

score: 10
Accepted
time: 2ms
memory: 3520kb

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.0061

result:

ok found '0.00610', expected '0.00608', error '0.00002'

Test #5:

score: 10
Accepted
time: 0ms
memory: 3628kb

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.0001

result:

ok found '0.00010', expected '0.00014', error '0.00004'

Test #6:

score: 10
Accepted
time: 0ms
memory: 3716kb

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.0001

result:

ok found '0.00010', expected '0.00010', error '0.00000'

Test #7:

score: 10
Accepted
time: 0ms
memory: 3632kb

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.0001

result:

ok found '0.00010', expected '0.00015', error '0.00005'

Test #8:

score: 10
Accepted
time: 2ms
memory: 3648kb

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.0002

result:

ok found '0.00020', expected '0.00024', error '0.00004'

Test #9:

score: 10
Accepted
time: 2ms
memory: 3564kb

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.0003

result:

ok found '0.00030', expected '0.00033', error '0.00003'

Test #10:

score: 10
Accepted
time: 1ms
memory: 3756kb

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.0001

result:

ok found '0.00010', expected '0.00011', error '0.00001'