#include <bits/stdc++.h>
#include "rainbow.h"
std::vector<std::vector<bool> > map_raw;
std::vector<std::pair<int, int> > blanks;
std::vector<std::pair<int, int> > blanks0;
std::vector<std::pair<int, int> > blanks1;
bool flag0 = false;
void init(int h, int w, int sx, int sy, int m, char *s) {
sx--;
sy--;
auto create_raw = [&] () {
map_raw.resize(h, std::vector<bool>(w, true));
int x = sx;
int y = sy;
map_raw[x][y] = false;
for (int i = 0; i < m; i++) {
if (s[i] == 'N') x--;
if (s[i] == 'S') x++;
if (s[i] == 'W') y--;
if (s[i] == 'E') y++;
map_raw[x][y] = false;
}
};;
if (h <= 50 && w <= 50) {
create_raw();
}
if (h == 2) {
create_raw();
{
int last = -1;
int prev = 0;
for (int i = 0; i <= w; i++) {
int cur = i < w ? (map_raw[0][i] | ((int) map_raw[1][i] << 1)) : 0;
// std::cerr << "! " << cur << " " << prev << std::endl;
if (prev & cur) {
prev = cur;
continue;
}
if (prev) blanks.push_back({last, i - 1});
if (cur) last = i;
prev = cur;
}
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < w; ) {
if (!map_raw[i][j]) j++;
else {
int t = j;
while (j < w && map_raw[i][j]) j++;
(i ? blanks1 : blanks0).push_back({t, j - 1});
}
}
}
flag0 = true;
}
}
int colour(int x0, int y0, int x1, int y1) {
/*
for (auto i : blanks) std::cerr << i.first << "," << i.second << " ";
std::cerr << std::endl;
for (auto i : blanks0) std::cerr << i.first << "," << i.second << " ";
std::cerr << std::endl;
for (auto i : blanks1) std::cerr << i.first << "," << i.second << " ";
std::cerr << std::endl;*/
x0--;
y0--;
if (flag0) {
auto &target = x1 == 1 ? blanks0 : x0 == 1 ? blanks1 : blanks;
auto itr0 = std::lower_bound(target.begin(), target.end(), std::pair<int, int>{y0, -1});
if (itr0 != target.begin() && std::prev(itr0)->second >= y0) itr0--;
auto itr1 = std::lower_bound(target.begin(), target.end(), std::pair<int, int>{y1, -1});
return itr1 - itr0;
} else if (map_raw.size()) {
std::vector<std::vector<bool> > used(map_raw.size(), std::vector<bool>(map_raw[0].size()));
std::queue<std::pair<int, int> > que;
int res = 0;
for (int x = x0; x < x1; x++) for (int y = y0; y < y1; y++) if (!used[x][y] && map_raw[x][y]) {
used[x][y] = true;
res++;
que.push({x, y});
while (que.size()) {
auto i = que.front();
que.pop();
std::pair<int, int> dd[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
for (auto d : dd) {
int x = i.first + d.first;
int y = i.second + d.second;
if (x < x0 || x >= x1 || y < y0 || y >= y1) continue;
if (!map_raw[x][y] || used[x][y]) continue;
used[x][y] = true;
que.push({x, y});
}
}
}
return res;
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
204 KB |
Output is correct |
2 |
Correct |
21 ms |
336 KB |
Output is correct |
3 |
Correct |
37 ms |
204 KB |
Output is correct |
4 |
Correct |
39 ms |
332 KB |
Output is correct |
5 |
Correct |
21 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
32 ms |
336 KB |
Output is correct |
12 |
Correct |
31 ms |
332 KB |
Output is correct |
13 |
Correct |
29 ms |
332 KB |
Output is correct |
14 |
Correct |
20 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
65 ms |
1080 KB |
Output is correct |
4 |
Correct |
68 ms |
1120 KB |
Output is correct |
5 |
Correct |
74 ms |
1476 KB |
Output is correct |
6 |
Correct |
70 ms |
1316 KB |
Output is correct |
7 |
Correct |
73 ms |
1568 KB |
Output is correct |
8 |
Correct |
60 ms |
1092 KB |
Output is correct |
9 |
Correct |
70 ms |
1092 KB |
Output is correct |
10 |
Correct |
79 ms |
1540 KB |
Output is correct |
11 |
Correct |
71 ms |
1364 KB |
Output is correct |
12 |
Correct |
57 ms |
1092 KB |
Output is correct |
13 |
Correct |
61 ms |
1152 KB |
Output is correct |
14 |
Correct |
71 ms |
1348 KB |
Output is correct |
15 |
Correct |
63 ms |
1392 KB |
Output is correct |
16 |
Correct |
61 ms |
1060 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
204 KB |
Output is correct |
2 |
Correct |
21 ms |
336 KB |
Output is correct |
3 |
Correct |
37 ms |
204 KB |
Output is correct |
4 |
Correct |
39 ms |
332 KB |
Output is correct |
5 |
Correct |
21 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
32 ms |
336 KB |
Output is correct |
12 |
Correct |
31 ms |
332 KB |
Output is correct |
13 |
Correct |
29 ms |
332 KB |
Output is correct |
14 |
Correct |
20 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Incorrect |
62 ms |
3892 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
204 KB |
Output is correct |
2 |
Correct |
21 ms |
336 KB |
Output is correct |
3 |
Correct |
37 ms |
204 KB |
Output is correct |
4 |
Correct |
39 ms |
332 KB |
Output is correct |
5 |
Correct |
21 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
32 ms |
336 KB |
Output is correct |
12 |
Correct |
31 ms |
332 KB |
Output is correct |
13 |
Correct |
29 ms |
332 KB |
Output is correct |
14 |
Correct |
20 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Incorrect |
62 ms |
3892 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |