Submission #1003401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003401		julian	Fliper (COCI22_fliper)	C++98	0 / 110	390 ms	60112 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;
}

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)) {
                    printPathResult(path);
                    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)) {
                    printPathResult(path);
                    return 0;
                }
			}
		}
	}

    std::cout << -1 << std::endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:149:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  149 |  for (auto& [y, obst] : ymap) {
      |             ^
Main.cpp:156:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  156 |  for (auto& [x, obst] : xmap) {
      |             ^
Main.cpp:170:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  170 |    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