#include <bits/stdc++.h>
#include "parks.h"
std::unordered_map<int, int> map[200001];
int N;
std::unordered_map<int, std::vector<int>> rely[200002];
std::vector<std::pair<int, int>> vld[200000];
std::pair<int, int> assigned[200000];
std::unordered_set<int> taken[200002];
time_t stop;
std::default_random_engine Rand(std::random_device{}());
bool shuffle = false;
bool Shuffle = false;
bool doomed(int x) {
for (auto a: vld[x]) if (!taken[a.first].count(a.second)) return false;
return true;
}
bool cantake(std::pair<int, int> a, int n) {
for (auto x: rely[a.first][a.second]) if (x > n && doomed(x)) return false;
return true;
}
bool backtrack(int n) {
if (n == N - 1) return true;
if (clock() > stop) return false;
// if (shuffle && vld[n].size() == 2 && Rand() % 2) {
// std::swap(vld[n][0], vld[n][1]);
// }
for (auto a: vld[n]) {
if (taken[a.first].count(a.second)) continue;
taken[a.first].insert(a.second);
if (!cantake(a, n)) {
taken[a.first].erase(a.second);
continue;
}
if (backtrack(n + 1)) {
assigned[n] = a;
return true;
}
taken[a.first].erase(a.second);
}
return false;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
stop = clock() + 3.4 * CLOCKS_PER_SEC;
N = (int) x.size();
if (N == 1) {
build({}, {}, {}, {});
return 1;
}
int maxx = x[0];
int minx = x[0];
int maxy = y[0];
int miny = y[0];
for (int i = 0; i < N; ++i) {
maxx = std::max(maxx, x[i]);
minx = std::min(minx, x[i]);
maxy = std::max(maxy, y[i]);
miny = std::min(miny, y[i]);
}
for (int i = 0; i < N; ++i) {
map[x[i]][y[i]] = i;
}
while (true) {
std::vector<int> u, v, a, b;
bool seen[N];
for (int i = 0; i < N; ++i) {
seen[i] = false;
}
std::queue<int> bfs;
int start = 0;
if (shuffle) start = Rand() % N;
bfs.push(start);
seen[start] = true;
auto add = [&](int x, int y, std::vector<int> &data) {
if (x < 0 || x > 200000) return;
if (map[x].count(y)) data.push_back(map[x][y]);
};
auto edges = [&](int x, int y) {
std::vector<int> result;
add(x, y + 2, result);
add(x, y - 2, result);
add(x + 2, y, result);
add(x - 2, y, result);
if (Shuffle) {
std::shuffle(result.begin(), result.end(), Rand);
}
return result;
};
int rem = N - 1;
while (!bfs.empty()) {
auto next = bfs.front();
bfs.pop();
for (auto n: edges(x[next], y[next])) {
if (!seen[n]) {
seen[n] = true;
bfs.push(n);
rem--;
u.push_back(next);
v.push_back(n);
}
}
}
if (rem)
return 0;
std::function<std::vector<std::pair<int, int>>(int, int)> valid = [&x, &y, minx, maxx, miny, maxy](int u,
int v) -> std::vector<std::pair<int, int>> {
if (x[u] == x[v]) {
int _y = (y[u] + y[v]) / 2;
if (x[u] == minx) return {{minx - 1, _y}};
if (x[u] == maxx) return {{maxx + 1, _y}};
return {{x[u] + 1, _y},
{x[u] - 1, _y}};
} else {
int _x = (x[u] + x[v]) / 2;
if (y[u] == miny) return {{_x, miny - 1}};
if (y[u] == maxy) return {{_x, maxy + 1}};
return {{_x, y[u] + 1},
{_x, y[u] - 1}};
}
};
if (shuffle) {
std::vector<std::pair<int, int>> Edges;
for (int i = 0; i < N - 1; ++i) {
Edges.emplace_back(u[i], v[i]);
}
std::sort(Edges.begin(), Edges.end(), [&](std::pair<int, int> a, std::pair<int, int> b) {
int A = a.first;
int B = b.first;
if (x[A] == x[B]) return y[A] < y[B];
return x[A] < x[B];
});
for (int i = 0; i < N - 1; ++i) {
u[i] = Edges[i].first;
v[i] = Edges[i].second;
}
}
for (int i = 0; i < N - 1; ++i) {
vld[i] = valid(u[i], v[i]);
if (Shuffle && vld[i].size() == 2 && Rand() % 2) {
std::swap(vld[i][0], vld[i][1]);
}
}
for (int i = 0; i < N - 1; ++i) {
for (auto n: vld[i]) {
rely[n.first][n.second].push_back(i);
}
}
if (backtrack(0)) {
for (int i = 0; i < N - 1; ++i) {
a.push_back(assigned[i].first);
b.push_back(assigned[i].second);
}
build(u, v, a, b);
return 1;
}
for (auto _x: x) {
rely[_x - 1].clear();
rely[_x + 1].clear();
}
if (clock() > stop) break;
Shuffle = shuffle;
shuffle = true;
#ifdef LOCAL
printf("Retrying...\n");
#endif
}
return 0;
}
