Submission #1003698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003698		julian	Fliper (COCI22_fliper)	C++98	0 / 110	376 ms	59192 KiB

Main

#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 (stderr)

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) {
      |        ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70