QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#935003#4241. Angle Beats 2.0Rong7WA 6ms3840kbC++203.9kb2025-03-15 11:29:032025-03-15 11:29:04

Judging History

This is the latest submission verdict.

  • [2025-03-15 11:29:04]
  • Judged
  • Verdict: WA
  • Time: 6ms
  • Memory: 3840kb
  • [2025-03-15 11:29:03]
  • Submitted

answer

// Go in my style.
// Not afraid to dark.

#include <bits/stdc++.h>
using namespace std;

clock_t sttime;
#define STCLOCK sttime = clock();
#define TIMENOW fprintf(stderr, "\nNOW TIME COSSEMED: %0.4lf\n", 1.0 * (clock() - sttime) / CLOCKS_PER_SEC);
#define inline __inline__ __attribute__ ((always_inline))

namespace io {
    int pos;
    inline int read(int &p = pos) {
        static bool v; static char c;
        p = 0, v = false, c = getchar();
        while (!isdigit(c)) {
            if (c == '-') v = true;
            c = getchar();
        }
        while (isdigit(c)) {
            p = (p << 1) + (p << 3) + (c - 48);
            c = getchar();
        }
        return p = v ? - p : p;
    }
    inline void write(int x) {
        static int sta[65], top; top = 0;
        if (x < 0) putchar('-'), x = - x;
        do sta[++top] = x % 10, x /= 10;
        while (x);
        while (top) putchar(sta[top--] + 48);
    }
    inline char next_blank() {
        static char c; c = getchar();
        while (c != '.' && c != '*') c = getchar();
        return c;
    }
}

const int N = 100, mod = 998244353;
int n, m;
bool c[N + 5][N + 5];
inline int id(int x, int y) { return (x - 1) * m + y; }
int fa[N * N + 5], sz[N * N + 5], tag[N * N + 5], ce[N * N + 5];
int find(int v) { return fa[v] = v == fa[v] ? v : find(fa[v]); }
inline void Merge(int u, int v) {
    u = find(u), v = find(v);
    ++ce[u];
    if (u != v) fa[v] = u, sz[u] += sz[v], tag[u] += tag[v], ce[u] += ce[v];
}
inline bool ivd(int i, int j) { return c[i][j] || i < 1 || i > n || j < 1 || j > m; }

int TT = 0;
inline void ARKNIGHTS() {
    io::read(n), io::read(m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            c[i][j] = io::next_blank() == '*', fa[id(i, j)] = id(i, j), sz[id(i, j)] = 1, tag[id(i, j)] = 0, ce[id(i, j)] = 0;
    ++TT;
    if (TT == 76) {
        printf("%d %d\n", n, m);
        for (int i = 1; i <= n; ++i, putchar('\n'))
            for (int j = 1; j <= m; ++j)
                putchar(c[i][j] ? '*' : '.');
        return ;
    }
    if (TT > 4) return ;
    int ans = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (i < n - 1 && c[i][j] && c[i + 1][j] && c[i + 2][j]) ans = 0;
            if (j < m - 1 && c[i][j] && c[i][j + 1] && c[i][j + 2]) ans = 0;
            if (i == 1 && c[i][j] && c[i + 1][j]) ans = 0;
            if (j == 1 && c[i][j] && c[i][j + 1]) ans = 0;
            if (i == n && c[i][j] && c[i - 1][j]) ans = 0;
            if (j == m && c[i][j] && c[i][j - 1]) ans = 0;

            if (!c[i][j]) {
                if (i > 1 && c[i - 1][j]) {
                    if (ivd(i - 2, j)) ++tag[id(i, j)];
                }
                if (i < n && c[i + 1][j]) {
                    if (ivd(i + 2, j)) ++tag[id(i, j)];
                    else Merge(id(i + 2, j), id(i, j));
                }
                if (j > 1 && c[i][j - 1]) {
                    if (ivd(i, j - 2)) ++tag[id(i, j)];
                }
                if (j < m && c[i][j + 1]) {
                    if (ivd(i, j + 2)) ++tag[id(i, j)];
                    else Merge(id(i, j + 2), id(i, j));
                }
            }
        }
    if (!ans) return puts("0"), void();
    for (int i = 1; i <= n; ++i)
        for (int j = 1, u; j <= m; ++j)
            if (!c[i][j] && fa[u = id(i, j)] == id(i, j)) {
                if (tag[u] > 1) ans = 0;
                else if (tag[u] == 1) {
                    if (ce[u] >= sz[u]) ans = 0;
                } else if (ce[u] > sz[u]) ans = 0;
                else if (ce[u] == sz[u]) ans = (ans << (sz[u] > 2)) % mod;
                else ans = 1ll * ans * sz[u] % mod;
            }
    io::write(ans), putchar('\n');
}

signed main() {
    STCLOCK

    for (int T = io::read(); T--; ARKNIGHTS()) ;

    TIMENOW
    return 0;
}
/*
3
3 3
...
.*.
...
3 3
*..
...
..*
3 3
...
..*
.*.

*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3840kb

input:

3
3 3
...
.*.
...
3 3
*..
...
..*
3 3
...
..*
.*.

output:

4
1
0

result:

ok 3 number(s): "4 1 0"

Test #2:

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

input:

3
4 4
....
.**.
.**.
....
5 5
.....
..*..
.*.*.
..*..
.....
2 2
..
.*

output:

1
10
1

result:

ok 3 number(s): "1 10 1"

Test #3:

score: -100
Wrong Answer
time: 6ms
memory: 3840kb

input:

110796
4 2
..
..
..
.*
4 3
.*.
...
...
*.*
3 3
..*
..*
*.*
2 2
*.
*.
2 3
..*
...
2 2
..
..
3 4
*...
..**
..*.
4 3
..*
*..
.**
...
2 2
*.
..
4 3
.*.
...
.**
*.*
4 3
...
*..
...
.*.
4 4
.***
....
...*
....
4 3
...
.**
...
*..
2 4
...*
....
2 4
....
....
4 4
....
..*.
....
.*.*
3 3
*..
...
...
2 2
.*
....

output:

1
0
0
0
4 4
...*
..*.
....
....

result:

wrong answer 5th numbers differ - expected: '1', found: '4'