QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#935003 | #4241. Angle Beats 2.0 | Rong7 | WA | 6ms | 3840kb | C++20 | 3.9kb | 2025-03-15 11:29:03 | 2025-03-15 11:29:04 |
Judging History
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'