QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21611 | #2841. 赛艇 | hy_zheng_zai_nei_juan# | AC ✓ | 2267ms | 266420kb | C++20 | 4.3kb | 2022-03-07 16:35:29 | 2022-05-08 03:42:39 |
Judging History
answer
#include <bits/stdc++.h>
const int N = 1e7 + 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: 0ms
memory: 9688kb
input:
5 5 5 00000 10000 00000 00000 01001 awdsw
output:
11
result:
ok single line: '11'
Test #2:
score: 0
Accepted
time: 74ms
memory: 25512kb
input:
500 500 50000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
77549
result:
ok single line: '77549'
Test #3:
score: 0
Accepted
time: 66ms
memory: 22580kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #4:
score: 0
Accepted
time: 72ms
memory: 22260kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #5:
score: 0
Accepted
time: 67ms
memory: 22968kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #6:
score: 0
Accepted
time: 69ms
memory: 23404kb
input:
500 500 750 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15625
result:
ok single line: '15625'
Test #7:
score: 0
Accepted
time: 378ms
memory: 70948kb
input:
1000 1000 300000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
83496
result:
ok single line: '83496'
Test #8:
score: 0
Accepted
time: 398ms
memory: 72628kb
input:
1000 1000 1000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
63001
result:
ok single line: '63001'
Test #9:
score: 0
Accepted
time: 372ms
memory: 69468kb
input:
1000 1000 1500 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
62500
result:
ok single line: '62500'
Test #10:
score: 0
Accepted
time: 2267ms
memory: 266388kb
input:
1500 1500 5000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
141376
result:
ok single line: '141376'
Test #11:
score: 0
Accepted
time: 2235ms
memory: 266420kb
input:
1500 1500 5000000 100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110...
output:
22801
result:
ok single line: '22801'
Test #12:
score: 0
Accepted
time: 4ms
memory: 9716kb
input:
2 2 4 00 01 dada
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 2187ms
memory: 265788kb
input:
1500 1500 5000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
141376
result:
ok single line: '141376'
Test #14:
score: 0
Accepted
time: 2050ms
memory: 251476kb
input:
1500 1500 2250 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
140625
result:
ok single line: '140625'
Test #15:
score: 0
Accepted
time: 3ms
memory: 10016kb
input:
50 60 20 000000000000000000000000010000000000000000000010000000000000 000000000000000000000000000000000000000000000000010000000000 000000000000000000000000000000000000000000010000000000001000 000000000000000000000000000000000100000000000000010000000000 00000000010000000000000000000000000000000000000...
output:
1633
result:
ok single line: '1633'
Test #16:
score: 0
Accepted
time: 2ms
memory: 9920kb
input:
60 50 500 00000000000000000000001000000000000000000100000000 00000000000000000000000010000000001000000000000000 00000000000000000000000000000000000000000000100000 00000000000000000000000000001000000000000010000000 00000000010000000000000000000000000000000000000000 00000000000000000000000000000000000...
output:
3
result:
ok single line: '3'
Test #17:
score: 0
Accepted
time: 69ms
memory: 26536kb
input:
500 500 500000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
15876
result:
ok single line: '15876'
Test #18:
score: 0
Accepted
time: 74ms
memory: 25024kb
input:
500 500 500 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
228475
result:
ok single line: '228475'
Test #19:
score: 0
Accepted
time: 62ms
memory: 22332kb
input:
500 500 1000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
53530
result:
ok single line: '53530'
Test #20:
score: 0
Accepted
time: 75ms
memory: 25292kb
input:
500 500 50000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
2
result:
ok single line: '2'
Test #21:
score: 0
Accepted
time: 68ms
memory: 22140kb
input:
500 500 100000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
9699
result:
ok single line: '9699'