| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1003698 |
2024-06-20T15:44:59 Z |
julian |
Fliper (COCI22_fliper) |
C++ |
|
376 ms |
59192 KB |
#include <bits/stdc++.h>
struct Obstacle {
size_t x, y;
char c;
bool visitedU = false, visitedD = false;
size_t prev = std::numeric_limits<size_t>::max();
size_t toL = std::numeric_limits<size_t>::max(), toR = std::numeric_limits<size_t>::max(), toT = std::numeric_limits<size_t>::max(), toB = std::numeric_limits<size_t>::max();
};
enum Dir {
UP,
DOWN,
LEFT,
RIGHT
};
size_t nmax = std::numeric_limits<size_t>::max();
char endingSide = '\0';
void dfs(size_t v, std::vector<Obstacle>& obstacles, Dir dir, std::vector<size_t>& path) {
path.push_back(v);
if (obstacles[v].c == '/') {
if (dir == UP || dir == RIGHT) {
endingSide = 'U';
if (obstacles[v].visitedU) return;
obstacles[v].visitedU = true;
} else {
endingSide = 'D';
if (obstacles[v].visitedD) return;
obstacles[v].visitedD = true;
}
if (dir == DOWN && obstacles[v].toL != nmax) {
dfs(obstacles[v].toL, obstacles, LEFT, path);
}
if (dir == UP && obstacles[v].toR != nmax) {
dfs(obstacles[v].toR, obstacles, RIGHT, path);
}
if (dir == RIGHT && obstacles[v].toT != nmax) {
dfs(obstacles[v].toT, obstacles, UP, path);
}
if (dir == LEFT && obstacles[v].toB != nmax) {
dfs(obstacles[v].toB, obstacles, DOWN, path);
}
}
if (obstacles[v].c == '\\') {
if (dir == UP || dir == RIGHT) {
endingSide = 'D';
if (obstacles[v].visitedD) return;
obstacles[v].visitedD = true;
} else {
endingSide = 'U';
if (obstacles[v].visitedU) return;
obstacles[v].visitedU = true;
}
if (dir == UP && obstacles[v].toL != nmax) {
dfs(obstacles[v].toL, obstacles, LEFT, path);
}
if (dir == DOWN && obstacles[v].toR != nmax) {
dfs(obstacles[v].toR, obstacles, RIGHT, path);
}
if (dir == LEFT && obstacles[v].toT != nmax) {
dfs(obstacles[v].toT, obstacles, UP, path);
}
if (dir == RIGHT && obstacles[v].toB != nmax) {
dfs(obstacles[v].toB, obstacles, DOWN, path);
}
}
}
void printPathResult(std::vector<size_t>& path) {
for (size_t v : path) {
std::cout << v + 1 << std::endl;
}
}
bool checkIfColoringPossible(std::vector<size_t>& path) {
std::unordered_map<size_t, size_t> m;
size_t i = 0;
for (size_t v : path) {
if (m.find(v) == m.end()) {
m[v] = i;
} else {
if (m[v] != i) return false;
}
i++;
i %= 4;
}
return true;
}
std::vector<size_t> getColoring(std::vector<size_t>& path) {
std::vector<size_t> color(path.size(), 200);
std::vector<size_t> counts(5, 0);
std::unordered_map<size_t, size_t> m;
size_t i = 1;
for (size_t j = 0; j < path.size(); j++) {
if (m.find(path[j]) == m.end()) {
m[path[j]] = i;
color[j] = i;
counts[i]++;
} else {
color[j] = m[path[j]];
counts[m[path[j]]]++;
}
// Set i to the minimum of counts, ensuring it ranges from 1 to 4
i = 1;
for (size_t k = 2; k <= 4; k++) {
if (counts[k] < counts[i]) {
i = k;
}
}
}
return color;
}
int main() {
size_t n;
std::cin >> n;
std::vector<Obstacle> obstacles(n);
for (size_t i = 0; i < n; i++) {
size_t x, y;
char c;
std::cin >> x >> y >> c;
obstacles[i] = {x, y, c};
}
std::vector<size_t> xsort(n), ysort(n);
for (size_t i = 0; i < n; i++) {
xsort[i] = ysort[i] = i;
}
std::sort(xsort.begin(), xsort.end(), [&](size_t a, size_t b) {
return obstacles[a].x < obstacles[b].x;
});
std::sort(ysort.begin(), ysort.end(), [&](size_t a, size_t b) {
return obstacles[a].y < obstacles[b].y;
});
std::unordered_map<size_t, std::vector<size_t>> ymap, xmap;
for (size_t i = 0; i < n; i++) {
if (ymap.find(obstacles[xsort[i]].y) == ymap.end()) {
ymap[obstacles[xsort[i]].y] = std::vector<size_t>(1, xsort[i]);
} else {
ymap[obstacles[xsort[i]].y].push_back(xsort[i]);
}
if (xmap.find(obstacles[ysort[i]].x) == xmap.end()) {
xmap[obstacles[ysort[i]].x] = std::vector<size_t>(1, ysort[i]);
} else {
xmap[obstacles[ysort[i]].x].push_back(ysort[i]);
}
}
for (auto& [y, obst] : ymap) {
for (size_t i = 0; i < obst.size() - 1; i++) {
obstacles[obst[i]].toR = obst[i + 1];
obstacles[obst[i + 1]].toL = obst[i];
}
}
for (auto& [x, obst] : xmap) {
for (size_t i = 0; i < obst.size() - 1; i++) {
obstacles[obst[i]].toT = obst[i + 1];
obstacles[obst[i + 1]].toB = obst[i];
}
}
std::vector<size_t> path;
for (size_t i = 0; i < n; i++) {
if (!obstacles[i].visitedD) {
path.clear();
dfs(i, obstacles, UP, path);
if (endingSide = 'D' && path.size() > 1 && path[0] == path[path.size() - 1] && (path.size() - 1) % 8 == 0) {
/*std::cout << "PATH" << std::endl;
for (size_t v : path) {
std::cout << obstacles[v].x << " " << obstacles[v].y << std::endl;
}*/
if (checkIfColoringPossible(path)) {
for (size_t a : getColoring(path)) {
std::cout << a << " ";
}
return 0;
}
}
}
if (!obstacles[i].visitedU) {
path.clear();
dfs(i, obstacles, DOWN, path);
if (endingSide == 'U' && path.size() > 1 && path[0] == path[path.size() - 1] && (path.size() - 1) % 8 == 0) {
/*std::cout << "PATH" << std::endl;
for (size_t v : path) {
std::cout << obstacles[v].x << " " << obstacles[v].y << std::endl;
}*/
if (checkIfColoringPossible(path)) {
for (size_t a : getColoring(path)) {
std::cout << a << " ";
}
return 0;
}
}
}
}
std::cout << -1 << std::endl;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:178:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
178 | for (auto& [y, obst] : ymap) {
| ^
Main.cpp:185:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
185 | for (auto& [x, obst] : xmap) {
| ^
Main.cpp:199:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
199 | if (endingSide = 'D' && path.size() > 1 && path[0] == path[path.size() - 1] && (path.size() - 1) % 8 == 0) {
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
376 ms |
59192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
