#include "rainbow.h"
#include <bits/stdc++.h>
void iterate(std::pair<int, int> &x, char c) {
if (c == 'N') {
--x.first;
}
if (c == 'S') {
++x.first;
}
if (c == 'E') {
++x.second;
}
if (c == 'W') {
--x.second;
}
}
struct UnionFind {
int n;
std::vector<int> data;
int components;
UnionFind(int n_) : n(n_), data(n, -1), components(n) {}
int find(int v) {
if (data[v] < 0) {
return v;
} else {
return data[v] = find(data[v]);
}
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) {
return;
}
if (data[a] > data[b]) {
std::swap(a, b);
}
data[a] += data[b];
data[b] = a;
--components;
}
int countGroups() {
return components;
}
};
int R, C, sR, sC, M;
int msR;
std::string S;
int T;
std::map<std::pair<int, int>, bool> dataMap;
std::vector<std::pair<int, int>> points;
std::array<std::vector<std::pair<int, int>>, 2> landRanges;
std::vector<std::pair<int, int>> vxRanges;
void init(int r, int c, int sr, int sc, int m, char *s) {
--sr, --sc;
R = r;
C = c;
sR = sr;
sC = sc;
msR = sr;
M = m;
S.resize(M);
for (int i = 0; i < M; ++i) {
S[i] = s[i];
}
// check...
if (R == 2) {
T = 2;
} else if (R <= 50 and C <= 50) {
T = 1;
} else {
T = 3;
}
auto add = [&](const std::pair<int, int> &v, bool type) {
if (type) {
dataMap[v] = true;
} else {
if (dataMap.find(v) == dataMap.end()) {
dataMap[v] = false;
}
}
};
std::pair<int, int> p = {sR, sC};
if (T == 2) {
add(p, true);
for (int i = 0; i < M; ++i) {
iterate(p, S[i]);
add(p, true);
};
for (int x = 0; x < 2; ++x) {
int l = 0;
for (int i = 0; i < C; ++i) {
if (dataMap[{x, i}]) {
if (l != i) {
landRanges[x].push_back({l, i - l});
}
l = i + 1;
}
}
if (l != C) {
landRanges[x].push_back({l, C - l});
}
}
int l = 0;
for (int i = 0; i < C; ++i) {
if (dataMap[{0, i}] and dataMap[{1, i}]) {
if (l != i) {
vxRanges.push_back({l, i - l});
}
l = i + 1;
}
}
if (l != C) {
vxRanges.push_back({l, C - l});
}
} else {
auto addBlock = [&](const std::pair<int, int> &v) {
add(v, true);
for (int ax = -1; ax <= 1; ++ax) {
for (int ay = -1; ay <= 1; ++ay) {
if (ax != 0 and ay != 0) {
continue;
}
if (ax == 0 and ay == 0) {
continue;
}
if (v.first + ax < 0 or v.first + ax >= R or v.second + ay < 0 or v.second + ay >= C) {
continue;
}
add({v.first + ax, v.second + ay}, false);
}
}
};
addBlock(p);
for (int i = 0; i < M; ++i) {
iterate(p, S[i]);
addBlock(p);
}
}
}
int colour(int ar, int ac, int br, int bc) {
--ar, --ac;
if (T == 2) {
const auto &ranges = (br - ar != 2 ? landRanges[ar] : vxRanges);
auto itr = std::lower_bound(ranges.begin(), ranges.end(), std::make_pair(ac, 0));
if (itr != ranges.begin()) {
--itr;
if (itr->first + itr->second <= ac) {
++itr;
}
}
auto itr2 = std::lower_bound(ranges.begin(), ranges.end(), std::make_pair(bc, 0));
return itr2 - itr;
} else {
auto add = [&](const std::pair<int, int> &v, bool type) {
if (type) {
dataMap[v] = true;
} else {
if (dataMap.find(v) == dataMap.end()) {
dataMap[v] = false;
}
}
};
for (int i = ac; i < bc; ++i) {
add({ar, i}, false);
add({br - 1, i}, false);
add({msR, i}, false);
}
for (int i = ar; i < br; ++i) {
add({i, ac}, false);
add({i, bc - 1}, false);
}
std::vector<std::pair<int, int>> ids;
int id = 0;
int countRiver = 0;
for (const auto &[pos, type] : dataMap) {
const auto &[x, y] = pos;
if (ar <= x and x < br and ac <= y and y < bc) {
ids.push_back(pos);
if (type) {
++countRiver;
}
}
}
std::sort(ids.begin(), ids.end());
ids.erase(std::unique(ids.begin(), ids.end()), ids.end());
auto getid = [&](const std::pair<int, int> &p) {
auto itr = std::lower_bound(ids.begin(), ids.end(), p);
if (*itr != p) {
return -1;
}
return (int)(itr - ids.begin());
};
UnionFind uft(ids.size());
for (int i = 0; i < (int)ids.size(); ++i) {
const auto &p = ids[i];
if (dataMap[p]) {
continue;
}
const auto &[x, y] = p;
for (int ax = -1; ax <= 1; ++ax) {
for (int ay = -1; ay <= 1; ++ay) {
if (ax != 0 and ay != 0) {
continue;
}
if (ax == 0 and ay == 0) {
continue;
}
const int nx = x + ax, ny = y + ay;
if (not(ar <= nx and nx < br and ac <= ny and ny < bc)) {
continue;
}
const int nid = getid({nx, ny});
if (nid == -1) {
continue;
}
if (not dataMap[{nx, ny}]) {
uft.merge(i, nid);
}
}
}
}
return uft.countGroups() - countRiver;
}
}
Compilation message
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:185:13: warning: unused variable 'id' [-Wunused-variable]
185 | int id = 0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
152 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
167 ms |
26140 KB |
Output is correct |
| 4 |
Correct |
174 ms |
26192 KB |
Output is correct |
| 5 |
Correct |
178 ms |
26476 KB |
Output is correct |
| 6 |
Correct |
220 ms |
26448 KB |
Output is correct |
| 7 |
Correct |
212 ms |
27076 KB |
Output is correct |
| 8 |
Correct |
171 ms |
26212 KB |
Output is correct |
| 9 |
Correct |
169 ms |
26188 KB |
Output is correct |
| 10 |
Correct |
173 ms |
26476 KB |
Output is correct |
| 11 |
Correct |
198 ms |
26476 KB |
Output is correct |
| 12 |
Correct |
174 ms |
26152 KB |
Output is correct |
| 13 |
Correct |
166 ms |
26268 KB |
Output is correct |
| 14 |
Correct |
167 ms |
26452 KB |
Output is correct |
| 15 |
Correct |
191 ms |
26452 KB |
Output is correct |
| 16 |
Correct |
170 ms |
26060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
566 ms |
43304 KB |
Output is correct |
| 3 |
Correct |
466 ms |
49552 KB |
Output is correct |
| 4 |
Incorrect |
381 ms |
30232 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
152 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
152 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
