QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#48228#3400. 重建feecle6418100 ✓3ms4588kbC++141.0kb2022-09-12 15:29:592022-09-12 15:30:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-12 15:30:01]
  • 评测
  • 测评结果:100
  • 用时:3ms
  • 内存:4588kb
  • [2022-09-12 15:29:59]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n;
double g[305][305];
double Det(double g[305][305]) {
	double ret=1,b[305][305]= {0};
	int sign=0;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++)b[i][j]=g[i][j];
	}
	for(int i=2; i<=n; i++) {
		if(!b[i][i]) {
			int j;
			for(j=i+1; j<=n; j++)if(fabs(b[j][i])>1e-7)break;
			if(j==n+1)return 0;
			for(int k=i; k<=n; k++)swap(b[i][k],b[j][k]);
			sign++;
		}
		ret*=b[i][i];
		for(int k=i+1; k<=n; k++)b[i][k]/=b[i][i];
		for(int j=i+1; j<=n; j++) {
			for(int k=i+1; k<=n; k++)b[j][k]-=b[j][i]*b[i][k];
		}
	}
	if(sign&1)return -ret;
	return ret;
}
int main() {
	scanf("%d",&n);
	double all=1;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			double x;
			scanf("%lf",&x);
			if(i==j)continue;
			if(x<1e-7)x=1e-7;
			if(x>1-1e-7)x=1-1e-7;
			if(i<j)all*=1-x;
			g[i][j]=x/(x-1),g[i][i]+=x/(1-x);
		}
	}
	printf("%.10lf\n",all*Det(g));
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

result:

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

Test #2:

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

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

result:

ok found '0.13884', expected '0.13884', error '0.00000'

Test #3:

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

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

result:

ok found '0.20187', expected '0.20187', error '0.00000'

Test #4:

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

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

result:

ok found '0.00608', expected '0.00608', error '0.00000'

Test #5:

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

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

result:

ok found '0.00014', expected '0.00014', error '0.00000'

Test #6:

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

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

result:

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

Test #7:

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

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

result:

ok found '0.00015', expected '0.00015', error '0.00000'

Test #8:

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

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

result:

ok found '0.00024', expected '0.00024', error '0.00000'

Test #9:

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

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

result:

ok found '0.00033', expected '0.00033', error '0.00000'

Test #10:

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

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

result:

ok found '0.00011', expected '0.00011', error '0.00000'