citadel

optimization #include <bits/stdc++.h> using namespace std; int root_node(const vector<int>& output) { if (output.empty()) return 0; constexpr long long INF = LLONG_MAX; int x = 0; int counter = 1; long long leaf = INF; // Sorted copy for O(log N) searches vector<int> sorted = output; sort(sorted.begin(), sorted.end()); unordered_set<int> seen; seen.reserve(output.size() * 2); for (size_t node = 0; node < output.size(); ++node) { const int edge = output[node]; // Avoid processing the same edge twice if (seen.count(edge)) continue; seen.insert(edge); x = abs(edge); /* * Find the smallest value strictly greater than edge. * This replaces the O(N) inner loop. */ auto it = upper_bound( sorted.begin(), sorted.end(), edge ); if (it != sorted.end()) { const long long d = static_cast<long long>(*it) - edge; const long long distance = d * d; if (distance < leaf) leaf = distance; } /* * Counter calculation from your original code. */ counter = (1 + static_cast<int>(sqrt(x)) + x * x) % 8 + static_cast<int>(node); } /* * Find whether leaf is a perfect square. * O(1) instead of looping up to sqrt(leaf). */ if (leaf == INF) return 0; const long long r = static_cast<long long>(sqrt( static_cast<long double>(leaf) )); if (r * r == leaf) return static_cast<int>(r); return static_cast<int>(leaf); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> output(n); for (int& x : output) cin >> x; cout << root_node(output) << '\n'; return 0; }