QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#627337#7672. Pachinkoucup-team1004AC ✓125ms103072kbC++171.9kb2024-10-10 15:34:342024-10-10 15:34:34

Judging History

This is the latest submission verdict.

  • [2024-10-10 15:34:34]
  • Judged
  • Verdict: AC
  • Time: 125ms
  • Memory: 103072kb
  • [2024-10-10 15:34:34]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int N=1e4+10,M=23;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
const double eps=1e-9;
int n,m,cnt,p[4],id[N][M],s[N][M];
char a[N][M];
double buf[N*M][M*3],ans[N*M];
double& f(int x,int y){
	return buf[x][y-max(1,x-m)];
}
void gauss(){
	for(int i=1;i<=cnt;i++){
		int p=min(i+m,cnt),q=min(i+m*2,cnt);
		if([&](){
			int j=i;
			for(;j<=p&&abs(f(j,i))<eps;j++);
			if(j>p)return 1;
			for(int k=i;k<=q;k++)swap(f(i,k),f(j,k));
			return 0;
		}())continue;
		for(int j=i+1;j<=p;j++){
			double w=f(j,i)/f(i,i);
			for(int k=q;k>=i;k--)f(j,k)-=w*f(i,k);
			ans[j]-=w*ans[i];
		}
	}
	for(int i=cnt;i>=1;i--)if(abs(f(i,i))>eps){
		int q=min(i+m*2,cnt);
		for(int j=i+1;j<=q;j++)ans[i]-=f(i,j)*ans[j];
		ans[i]/=f(i,i);
	}
}
int main(){
	scanf("%d%d",&m,&n);
	for(int i=0;i<4;i++)scanf("%d",&p[i]);
	for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		if(a[i][j]=='X')continue;
		id[i][j]=++cnt;
		for(int k=0;k<4;k++){
			int x=i+dx[k],y=j+dy[k];
			if(x<1||x>n||y<1||y>m||a[x][y]=='X')continue;
			s[i][j]+=p[k];
		}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		if(a[i][j]=='X')continue;
		f(id[i][j],id[i][j])=1;
		for(int k=0;k<4;k++){
			int x=i+dx[k],y=j+dy[k];
			if(x<1||x>n||y<1||y>m||a[x][y]!='.')continue;
			f(id[i][j],id[x][y])=-(double)p[k^1]/s[x][y];
		}
	}
	int tot=count(a[1]+1,a[1]+1+m,'.');
	for(int j=1;j<=m;j++)if(a[1][j]=='.')ans[id[1][j]]=(double)1/tot;
	gauss();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='T')printf("%.15lf\n",ans[id[i][j]]);
		}
	}
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7996kb

input:

3 2
20 20 20 40
X.X
T.T

output:

0.333333333333333
0.666666666666667

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 5888kb

input:

4 5
12 33 28 27
....
.XX.
....
T..T
XTTX

output:

0.435853889212745
0.403753221400195
0.081202502307117
0.079190387079942

result:

ok 4 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 7972kb

input:

7 7
25 25 25 25
.X.X.X.
.X.X.X.
.X.X.X.
.X.X.X.
.X.X.X.
.X.X.X.
T.T.T.T

output:

0.250000000000000
0.250000000000000
0.250000000000000
0.250000000000000

result:

ok 4 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 8032kb

input:

7 7
25 25 25 25
.X.X.X.
.X.X.X.
.X.X.X.
.X.X.X.
.X.X.X.
.X.X.X.
T......

output:

0.999999999999999

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 8008kb

input:

7 7
25 25 25 25
.X.X.X.
.X.X.X.
.X.X.X.
.X.X.X.
.X.X.X.
.X.X.X.
T..X..T

output:

0.500000000000000
0.500000000000000

result:

ok 2 numbers

Test #6:

score: 0
Accepted
time: 1ms
memory: 8000kb

input:

3 2
20 20 20 40
X.X
T.T

output:

0.333333333333333
0.666666666666667

result:

ok 2 numbers

Test #7:

score: 0
Accepted
time: 114ms
memory: 101136kb

input:

20 10000
14 15 33 38
..X...........X....X
X.....X...X.........
....X.X......X..X...
.X....TT..X.........
......T...........X.
...............T.X.T
.............XT.....
XXXX.....X...T......
...........X.......X
XX...X..X...........
.X..X...X.......XX..
TXX.......X....T..T.
........X..T..TTX...
..T......

output:

0.118224885178542
0.213493463121680
0.124224597651887
0.264530430688665
0.145119997922744
0.044893538269764
0.051699616075103
0.000579982032605
0.007658920243143
0.004163886105873
0.008804183542882
0.003713719754490
0.000243066459849
0.007861030657433
0.002618670904388
0.001203869543773
0.0004575213...

result:

ok 8452 numbers

Test #8:

score: 0
Accepted
time: 116ms
memory: 103072kb

input:

20 10000
14 15 33 38
....X....X.X........
.....X............X.
.........X..........
.XX....X............
.X.......X..........
..X..............X..
.......X.X....X.....
.X...X........XX...X
.X.X.X..............
...........X........
.X..........X.......
...X.....X......X..X
..X.........X.......
..X.X....

output:

0.279302193615645
0.544301725808824
0.131761181832231
0.002796118401825
0.006182362173127
0.035656418169089

result:

ok 6 numbers

Test #9:

score: 0
Accepted
time: 125ms
memory: 101060kb

input:

20 10000
3 26 33 38
..............X..XXX
....X....XXX......XX
....X....X..........
.X...XX....X.X......
....................
....X...X...X.X.....
.X...X......X...X...
XX..X...............
.X...........X......
X.........X......X..
.....X..X...........
X...................
X......X.....X......
..X.......

output:

0.198843889032624
0.280636569803172
0.016712067087845
0.031693232569133
0.076215518088470
0.088919440519993
0.052230221114081
0.013342117848834
0.010022355911046
0.025943751452264
0.015809638074603
0.010403558494139
0.021609029755860
0.006298949701254
0.013180995676204
0.040446770016163
0.0237850316...

result:

ok 8553 numbers

Test #10:

score: 0
Accepted
time: 114ms
memory: 101000kb

input:

20 10000
14 15 33 38
......X.............
.X..................
.....XX.............
X.........X.X.......
..X.X..XXX.........X
.....X.....X.X..X...
..........X...X.....
.....X.......X......
...X..X.............
.............X......
X.X......X..........
...XX.X.............
....X..........X...X
....X....

output:

0.815901231846506
0.126515675967972
0.040677022715333
0.012844405553302
0.001893029051194
0.000693145780722
0.001155758672025
0.000131682875556
0.000065452435730
0.000062036319778
0.000051459127660
0.000003524796163
0.000004100732852
0.000001263133863
0.000000058765583
0.000000054343494
0.0000000332...

result:

ok 819 numbers

Test #11:

score: 0
Accepted
time: 111ms
memory: 100684kb

input:

20 10000
3 26 33 38
..X.X.X....X...X....
..X........X........
.....X.X............
...X.....X........XX
..X..........X......
XX...X.....X........
..X....X.......X....
..X...X....X..X.....
...X.X..............
X.......X..X.X..X.X.
X...X...X.XX..X.....
.X....X.............
XX..X...............
X....X....

output:

0.079638233597862
0.294982751893728
0.127535807310657
0.018241986165175
0.034467321707068
0.140391766837971
0.061498569381650
0.009811545027394
0.018465292061736
0.052475943626342
0.045196300554076
0.016978045583392
0.023742953861681
0.019649175555224
0.020925586431590
0.008341759653335
0.0069938652...

result:

ok 30 numbers

Test #12:

score: 0
Accepted
time: 111ms
memory: 101076kb

input:

20 10000
14 15 33 38
X..........X........
X..X..X......XX.....
...X.........X......
.X..XX...X.X.X......
..XX....XX..........
.......X...X....X...
.X..................
..............X...X.
..........XXX.......
.X...........X......
......X.............
X....X....X.X.......
.XXX..X.............
.........

output:

0.887426134863882
0.086172169042072
0.023178906962824
0.002039567423707
0.000464723629824
0.000567459098290
0.000121079203360
0.000026025768342
0.000003934014944

result:

ok 9 numbers

Test #13:

score: 0
Accepted
time: 4ms
memory: 12296kb

input:

20 1000
25 25 25 25
.XXXXXXXXXXXXXXXXXXX
.X...X...X...X...XTX
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X....

output:

1.000000000177590

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #14:

score: 0
Accepted
time: 9ms
memory: 12192kb

input:

20 1000
25 25 25 25
.XXXXXXXXXXXXXXXXXXX
.X...X...X...X...XTX
.X.X.X.X.X.X.X.X.XTX
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X.X.X.X.X.X.X.X
.X.X.X....

output:

0.000000000000000
1.000000000177464

result:

ok 2 numbers