QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#627337 | #7672. Pachinko | ucup-team1004 | AC ✓ | 125ms | 103072kb | C++17 | 1.9kb | 2024-10-10 15:34:34 | 2024-10-10 15:34:34 |
Judging History
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