QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#498286#7672. PachinkoMax_s_xaMAC ✓158ms106168kbC++144.7kb2024-07-30 11:10:462024-07-30 11:10:46

Judging History

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

  • [2024-07-30 11:10:46]
  • 评测
  • 测评结果:AC
  • 用时:158ms
  • 内存:106168kb
  • [2024-07-30 11:10:46]
  • 提交

answer

#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>

typedef long long ll;
typedef double lf;

// #define DEBUG 1
struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    #if DEBUG
    #else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
    #endif
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
    #define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')

    template <typename T>
    void Read(T &x)
    {
        #if DEBUG
        std::cin >> x;
        #else
        bool sign = 0; char ch = gc(); x = 0;
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
        if (sign) x = -x;
        #endif
    }
    void Read(char *s)
    {
        #if DEBUG
        std::cin >> s;
        #else
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
        #endif
    }
    void Read(char &c) {for (c = gc(); blank(c); c = gc());}

    void Push(const char &c)
    {
        #if DEBUG
        putchar(c);
        #else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
        #endif
    }
    template <typename T>
    void Write(T x)
    {
        if (x < 0) x = -x, Push('-');
        static T sta[35];
        int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) Push(sta[--top] ^ 48);
    }
    template <typename T>
    void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)

using namespace std;

const int MAXN = 1e4 + 10, MAXM = 2e5 + 10;
const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
const int dx2[4] = {1, -1, 0, 0}, dy2[4] = {0, 0, 1, -1};
const lf eps = 1e-9;

int n, m, pb[4], sum[MAXM];
char mp[MAXN][22];

inline int Tr(int i, int j) { return (i - 1) * m + j; }

lf f[MAXM][62], g[MAXM]; int bg[MAXM];
inline lf &F(int x, int y) { return f[x][y - bg[x]]; }

inline void Gauss()
{
    for (int i = 1; i <= n * m; i++)
    {
        int r = min(n * m, i + m), R = min(n * m, i + 2 * m), p = i;
        for (int j = i; j <= r; j++)
            if (fabs(F(j, i)) > fabs(F(p, i))) p = j;
        if (fabs(F(p, i)) < eps) continue;
        if (p != i)
        {
            swap(g[i], g[p]);
            for (int j = i; j <= R; j++)
                swap(F(i, j), F(p, j));
        }
        g[i] /= F(i, i);
        for (int j = R; j >= i; j--) F(i, j) /= F(i, i);
        for (int j = i + 1; j <= r; j++)
        {
            g[j] -= g[i] * F(j, i);
            for (int k = R; k >= i; k--) F(j, k) -= F(i, k) * F(j, i);
        }
    }
    for (int i = n * m; i >= 1; i--)
    {
        if (fabs(F(i, i)) < eps) continue;
        for (int j = max(1, i - 2 * m); j < i; j++)
            g[j] -= g[i] * F(j, i);
    }
}

int main()
{
    // freopen("A.in", "r", stdin);
    // freopen("A.out", "w", stdout);
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    Read(m), Read(n);
    for (int i = 0; i < 4; i++) Read(pb[i]);
    for (int i = 1; i <= n; i++) Read(mp[i] + 1);
    int cnt = 0;
    for (int i = 1; i <= m; i++) cnt += (mp[1][i] == '.');
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (mp[i][j] == '.')
            {
                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 || mp[x][y] == 'X') continue;
                    sum[Tr(i, j)] += pb[k];
                }
            }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            bg[Tr(i, j)] = max(1, Tr(i - 1, j));
            F(Tr(i, j), Tr(i, j)) = 1;
            if (i == 1 && mp[i][j] == '.') g[Tr(i, j)] = 1.0 / cnt;
            if (mp[i][j] == 'X') continue;
            for (int k = 0; k < 4; k++)
            {
                int x = i + dx2[k], y = j + dy2[k];
                if (x < 1 || x > n || y < 1 || y > m || mp[x][y] != '.') continue;
                F(Tr(i, j), Tr(x, y)) = -(lf)pb[k] / sum[Tr(x, y)];
            }
        }
    Gauss();
    cout << fixed << setprecision(10);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (mp[i][j] == 'T')
                cout << g[Tr(i, j)] << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

0.3333333333
0.6666666667

result:

ok 2 numbers

Test #2:

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

input:

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

output:

0.4358538892
0.4037532214
0.0812025023
0.0791903871

result:

ok 4 numbers

Test #3:

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

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.2500000000
0.2500000000
0.2500000000
0.2500000000

result:

ok 4 numbers

Test #4:

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

output:

1.0000000000

result:

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

Test #5:

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

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.5000000000
0.5000000000

result:

ok 2 numbers

Test #6:

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

input:

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

output:

0.3333333333
0.6666666667

result:

ok 2 numbers

Test #7:

score: 0
Accepted
time: 152ms
memory: 105064kb

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.1182248852
0.2134934631
0.1242245977
0.2645304307
0.1451199979
0.0448935383
0.0516996161
0.0005799820
0.0076589202
0.0041638861
0.0088041835
0.0037137198
0.0002430665
0.0078610307
0.0026186709
0.0012038695
0.0004575213
0.0002715256
0.0000618941
0.0001081730
0.0000296441
0.0000119834
0.0000030366
0...

result:

ok 8452 numbers

Test #8:

score: 0
Accepted
time: 151ms
memory: 105936kb

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.2793021936
0.5443017258
0.1317611818
0.0027961184
0.0061823622
0.0356564182

result:

ok 6 numbers

Test #9:

score: 0
Accepted
time: 158ms
memory: 104664kb

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.1988438890
0.2806365698
0.0167120671
0.0316932326
0.0762155181
0.0889194405
0.0522302211
0.0133421178
0.0100223559
0.0259437515
0.0158096381
0.0104035585
0.0216090298
0.0062989497
0.0131809957
0.0404467700
0.0237850317
0.0073096045
0.0211674150
0.0040835563
0.0113147435
0.0004484085
0.0005747064
0...

result:

ok 8553 numbers

Test #10:

score: 0
Accepted
time: 154ms
memory: 105316kb

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.8159012318
0.1265156760
0.0406770227
0.0128444056
0.0018930291
0.0006931458
0.0011557587
0.0001316829
0.0000654524
0.0000620363
0.0000514591
0.0000035248
0.0000041007
0.0000012631
0.0000000588
0.0000000543
0.0000000332
0.0000000176
0.0000000356
0.0000000091
0.0000000012
0.0000000006
0.0000000002
0...

result:

ok 819 numbers

Test #11:

score: 0
Accepted
time: 154ms
memory: 104760kb

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.0796382336
0.2949827519
0.1275358073
0.0182419862
0.0344673217
0.1403917668
0.0614985694
0.0098115450
0.0184652921
0.0524759436
0.0451963006
0.0169780456
0.0237429539
0.0196491756
0.0209255864
0.0083417597
0.0069938652
0.0011921559
0.0027725088
0.0005076385
0.0014612201
0.0041895809
0.0012465144
0...

result:

ok 30 numbers

Test #12:

score: 0
Accepted
time: 148ms
memory: 106168kb

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.8874261349
0.0861721690
0.0231789070
0.0020395674
0.0004647236
0.0005674591
0.0001210792
0.0000260258
0.0000039340

result:

ok 9 numbers

Test #13:

score: 0
Accepted
time: 16ms
memory: 18324kb

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

result:

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

Test #14:

score: 0
Accepted
time: 15ms
memory: 20528kb

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.0000000000
1.0000000002

result:

ok 2 numbers