QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21609 | #2841. 赛艇 | hy_zheng_zai_nei_juan# | RE | 384ms | 73924kb | C++20 | 4.3kb | 2022-03-07 16:33:12 | 2022-05-08 03:42:30 |
Judging History
answer
#include <bits/stdc++.h>
const int N = 4e6 + 50;
const int mod = 998244353;
const int g = 3;
inline int inc(int x, int y) { x += y - mod; return x + (x >> 31 & mod); }
inline int dec(int x, int y) { x -= y; return x + (x >> 31 & mod); }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline int fastpow(int x, int p)
{
int r = 1;
while (p)
{
if (p & 1) r = mul(r, x);
x = mul(x, x);
p >>= 1;
}
return r;
}
struct NTT
{
int omega[N], omegaInv[N], rev[N], len, k;
inline void init(int n)
{
len = 1, k = 0;
while (len <= n) len <<= 1, ++k;
for (int i = 0; i < len; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
const int t = fastpow(g, (mod - 1) / len);
omega[0] = omegaInv[0] = 1;
for (int i = 1; i < len; ++i) omega[i] = omegaInv[len - i] = mul(omega[i - 1], t);
}
inline void DFT(int *a, const int *w)
{
for (int i = 1; i < len; ++i) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
for (int h = 1; h < len; h <<= 1)
for (int t = len / (h << 1), j = 0; j < len; j += (h << 1))
{
const int *wn = w; int *x = a + j, *y = a + j + h;
for (int i = j; i < j + h; ++i)
{
int _1 = *x, _2 = mul(*y, *wn);
*x++ = inc(_1, _2);
*y++ = dec(_1, _2);
wn += t;
}
}
if (w == omegaInv)
{
const int t = mod - (mod - 1) / len;
for (int i = 0; i < len; ++i) a[i] = mul(a[i], t);
}
}
inline void operator()(std::vector<int> &_, int op)
{
if (_.size() < len) _.resize(len);
if (op == 1) DFT(_.data(), omega);
else DFT(_.data(), omegaInv);
assert(_.size() >= len);
}
} ntt;
struct Poly
{
std::vector<int> _;
Poly(){}
Poly(const std::vector<int> &_) : _(_) {}
inline int& operator[](int k)
{
if (_.size() <= k) _.resize(k + 1);
return _[k];
}
inline int operator[](int k) const
{
if (_.size() <= k) return 0;
return _[k];
}
inline int deg() const
{
return (int)_.size() - 1;
}
};
template <int T>
struct fast_io
{
char p[T], q[T], * p1, * p2, * q1, * q2;
fast_io()
{
p1 = p2 = p;
q1 = q, q2 = q + T;
}
inline char gc()
{
return p1 == p2 && (p2 = (p1 = p) + fread(p, 1, T, stdin), p1 == p2) ? EOF : *p1++;
}
inline void pc(char c)
{
if (q1 == q2) q2 = (q1 = q) + fwrite(q, 1, T, stdout);
*q1++ = c;
}
~fast_io()
{
fwrite(q, 1, q1 - q, stdout);
}
};
fast_io<1 << 20> io;
inline int read()
{
int res = 0;
char ch;
do ch = io.gc(); while (ch < 48 || ch > 57);
do res = res * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57);
return res;
}
inline void put(int64_t x)
{
if (x < 0) io.pc('-'), x = -x;
if (x >= 10) put(x / 10);
io.pc(48 + x % 10);
}
inline void output(int64_t x, char ch = ' ')
{
put(x);
io.pc(ch);
}
inline Poly operator*(const Poly &A, const Poly &B)
{
int d1 = A.deg(), d2 = B.deg();
std::vector<int> a = A._, b = B._;
ntt.init(d1 + d2 + 1);
ntt(a, 1), ntt(b, 1);
std::vector<int> c(ntt.len);
for (int i = 0; i < ntt.len; ++i) c[i] = mul(a[i], b[i]);
ntt(c, -1);
return Poly(c);
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
Poly A, B;
int n, m, k;
std::cin >> n >> m >> k;
std::string s;
auto id = [&](int i, int j) {
return (i - 1) * m + j;
};
auto dir = [&](char ch) -> std::pair<int, int> {
if (ch == 's') return {1, 0};
if (ch == 'w') return {-1, 0};
if (ch == 'd') return {0, 1};
if (ch == 'a') return {0, -1};
throw;
};
for (int i = 1; i <= n; ++i) {
std::cin >> s;
for (int j = 1; j <= m; ++j) {
A[id(i, j)] = (s[j - 1] == '1');
}
}
std::cin >> s;
int len = s.length();
int curx = 1, cury = 1;
int minx = 1, miny = 1;
for (int i = 0; i < len; ++i) {
auto [x, y] = dir(s[i]);
curx += x, cury += y;
minx = std::min(minx, curx);
miny = std::min(miny, cury);
}
int tx = 2 - minx, ty = 2 - miny;
int maxx = tx, maxy = ty;
B[n * m - id(tx, ty) + 1] = 1;
curx = tx, cury = ty;
for (int i = 0; i < len; ++i) {
auto [x, y] = dir(s[i]);
curx += x, cury += y;
maxx = std::max(maxx, curx);
maxy = std::max(maxy, cury);
B[n * m - id(curx, cury) + 1] = 1;
}
Poly C = A * B;
int ans = 0;
for (int i = 1; i <= n - maxx + 1; ++i)
for (int j = 1; j <= m - maxy + 1; ++j)
if (C[n * m + id(i, j)] == 0)
++ans;
std::cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9868kb
input:
5 5 5 00000 10000 00000 00000 01001 awdsw
output:
11
result:
ok single line: '11'
Test #2:
score: 0
Accepted
time: 79ms
memory: 24496kb
input:
500 500 50000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
77549
result:
ok single line: '77549'
Test #3:
score: 0
Accepted
time: 62ms
memory: 23956kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #4:
score: 0
Accepted
time: 65ms
memory: 23368kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #5:
score: 0
Accepted
time: 63ms
memory: 24848kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #6:
score: 0
Accepted
time: 80ms
memory: 24756kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #7:
score: 0
Accepted
time: 357ms
memory: 71592kb
input:
1000 1000 300000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
83496
result:
ok single line: '83496'
Test #8:
score: 0
Accepted
time: 384ms
memory: 73924kb
input:
1000 1000 1000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
63001
result:
ok single line: '63001'
Test #9:
score: 0
Accepted
time: 367ms
memory: 70364kb
input:
1000 1000 1500 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
62500
result:
ok single line: '62500'
Test #10:
score: -100
Runtime Error
input:
1500 1500 5000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...