#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define ff first
#define ss second
const int N = 800 + 10, K = 1e5 + 9;
const int dx[4] = { 0, 0, -1, 1 };
const int dy[4] = { -1, 1, 0, 0 };
int m, n, k;
int u[N][N];
char c[K << 1];
int op[256], cnt[16], ma[16];
void init() {
op['E'] = 0, op['W'] = 1, op['S'] = 2, op['N'] = 3;
while (k < K) {
copy(c, c + k, c + k);
k <<= 1;
}
for (int i = 1, x; i < k; ++i) {
x = op[c[i]];
for (int msk = 1; msk < 16; ++msk)
if (msk >> x & 1)
ma[msk] = max(ma[msk], ++cnt[msk]);
else cnt[msk] = 0;
}
}
bool vis[N][N];
bool check(int x, int y) {
return 0 < x && x <= m && 0 < y && y <= n && u[x][y] && !vis[x][y];
}
int getmsk(int x, int y) {
int msk = 0;
for (int i = 0; i < 4; ++i) {
int xx = x - dx[i], yy = y - dy[i];
msk |= vis[xx][yy] << i;
}
return msk;
}
int calc(int x, int y) {
if (m <= 50 && n <= 50)
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) vis[i][j] = false;
queue<pii> q;
q.emplace(x, y);
vis[x][y] = true;
int cnt(0);
while (!q.empty()) {
pii tmp = q.front(); q.pop();
++cnt;
for (int i = 0; i < 4; ++i) {
x = tmp.ff + dx[i], y = tmp.ss + dy[i];
if (!check(x, y)) continue;
int msk = getmsk(x, y);
if (ma[msk] >= u[x][y]) {
vis[x][y] = true;
q.emplace(x, y);
}
}
}
return cnt;
}
void subtask2() {
int mi(m * n + 1), cnt(0);
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) if (u[i][j]) {
int x = calc(i, j);
if (mi > x) mi = x, cnt = 1;
else if (mi == x) ++cnt;
}
cout << mi << ' ' << cnt << '\n';
}
int l[N], r[N];
void subtask1() {
int mi(n + 1), _cnt(0);
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j)
l[j] = !u[i][j] ? 0 : ma[1] >= u[i][j - 1] ? l[j - 1] + 1 : 1;
for (int j = n; j; --j)
r[j] = !u[i][j] ? 0 : ma[2] >= u[i][j + 1] ? r[j + 1] + 1 : 1;
for (int j = 1; j <= n; ++j) if (u[i][j]) {
int len = l[j] + r[j] - 1;
if (mi > len) mi = len, _cnt = 1;
else if (mi == len) ++_cnt;
}
}
cout << mi << ' ' << _cnt << '\n';
}
int main() {
cin.tie(NULL)->sync_with_stdio(false);
cin >> k >> m >> n >> c;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) cin >> u[i][j];
init();
if (m <= 50 && n <= 50)
subtask2();
else subtask1();
}
/** /\_/\
* (= ._.)
* / >0 \>1
**/
Compilation message
virus.cpp: In function 'void init()':
virus.cpp:26:19: warning: array subscript has type 'char' [-Wchar-subscripts]
26 | x = op[c[i]];
| ~~~^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
468 KB |
Output is correct |
2 |
Correct |
39 ms |
2940 KB |
Output is correct |
3 |
Correct |
53 ms |
2900 KB |
Output is correct |
4 |
Correct |
38 ms |
4168 KB |
Output is correct |
5 |
Correct |
53 ms |
6668 KB |
Output is correct |
6 |
Correct |
5 ms |
3028 KB |
Output is correct |
7 |
Correct |
43 ms |
4400 KB |
Output is correct |
8 |
Correct |
28 ms |
3544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
468 KB |
Output is correct |
2 |
Correct |
5 ms |
468 KB |
Output is correct |
3 |
Correct |
6 ms |
468 KB |
Output is correct |
4 |
Correct |
5 ms |
468 KB |
Output is correct |
5 |
Correct |
7 ms |
468 KB |
Output is correct |
6 |
Correct |
202 ms |
724 KB |
Output is correct |
7 |
Correct |
5 ms |
468 KB |
Output is correct |
8 |
Correct |
7 ms |
724 KB |
Output is correct |
9 |
Correct |
128 ms |
608 KB |
Output is correct |
10 |
Correct |
4 ms |
468 KB |
Output is correct |
11 |
Correct |
12 ms |
696 KB |
Output is correct |
12 |
Correct |
300 ms |
616 KB |
Output is correct |
13 |
Correct |
105 ms |
692 KB |
Output is correct |
14 |
Correct |
100 ms |
724 KB |
Output is correct |
15 |
Correct |
106 ms |
724 KB |
Output is correct |
16 |
Correct |
92 ms |
724 KB |
Output is correct |
17 |
Correct |
8 ms |
692 KB |
Output is correct |
18 |
Correct |
15 ms |
596 KB |
Output is correct |
19 |
Correct |
8 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
468 KB |
Output is correct |
2 |
Correct |
39 ms |
2940 KB |
Output is correct |
3 |
Correct |
53 ms |
2900 KB |
Output is correct |
4 |
Correct |
38 ms |
4168 KB |
Output is correct |
5 |
Correct |
53 ms |
6668 KB |
Output is correct |
6 |
Correct |
5 ms |
3028 KB |
Output is correct |
7 |
Correct |
43 ms |
4400 KB |
Output is correct |
8 |
Correct |
28 ms |
3544 KB |
Output is correct |
9 |
Correct |
5 ms |
468 KB |
Output is correct |
10 |
Correct |
5 ms |
468 KB |
Output is correct |
11 |
Correct |
6 ms |
468 KB |
Output is correct |
12 |
Correct |
5 ms |
468 KB |
Output is correct |
13 |
Correct |
7 ms |
468 KB |
Output is correct |
14 |
Correct |
202 ms |
724 KB |
Output is correct |
15 |
Correct |
5 ms |
468 KB |
Output is correct |
16 |
Correct |
7 ms |
724 KB |
Output is correct |
17 |
Correct |
128 ms |
608 KB |
Output is correct |
18 |
Correct |
4 ms |
468 KB |
Output is correct |
19 |
Correct |
12 ms |
696 KB |
Output is correct |
20 |
Correct |
300 ms |
616 KB |
Output is correct |
21 |
Correct |
105 ms |
692 KB |
Output is correct |
22 |
Correct |
100 ms |
724 KB |
Output is correct |
23 |
Correct |
106 ms |
724 KB |
Output is correct |
24 |
Correct |
92 ms |
724 KB |
Output is correct |
25 |
Correct |
8 ms |
692 KB |
Output is correct |
26 |
Correct |
15 ms |
596 KB |
Output is correct |
27 |
Correct |
8 ms |
724 KB |
Output is correct |
28 |
Incorrect |
40 ms |
4344 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |