Download docker_space/frontier_cs_10/examples/gpt5_4.cpp from JustinTX/shinka-backup: direct link, hf CLI and curl.
- Browser
- Download file 5.15 kB
-
https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/gpt5_4.cpp
- Command line
-
hf download hf://JustinTX/shinka-backup/docker_space/frontier_cs_10/examples/gpt5_4.cpp
-
curl -L -o gpt5_4.cpp https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/gpt5_4.cpp
5.15 kB
| using namespace std; | |
| using ll = long long; | |
| using ull = unsigned long long; | |
| // Global distance cache: pair (min(u,v), max(u,v)) -> distance | |
| static unordered_map<ull, ll> distCache; | |
| // Edge set to avoid duplicates | |
| static unordered_set<ull> edgeSet; | |
| static vector<tuple<int,int,ll>> edges; | |
| static int n; | |
| // Pack a pair (u,v) with u < v into 64-bit key | |
| inline ull packKey(int u, int v) { | |
| if (u > v) swap(u, v); | |
| return ( (ull)u << 32 ) | (ull)v; | |
| } | |
| ll getDist(int u, int v) { | |
| if (u == v) return 0; | |
| ull key = packKey(u, v); | |
| auto it = distCache.find(key); | |
| if (it != distCache.end()) return it->second; | |
| cout << "? " << u << " " << v << endl; | |
| cout.flush(); | |
| ll ans; | |
| if (!(cin >> ans)) { | |
| // In case of input failure, exit gracefully | |
| exit(0); | |
| } | |
| distCache.emplace(key, ans); | |
| return ans; | |
| } | |
| inline void setCachedDist(int u, int v, ll d) { | |
| if (u == v) return; | |
| ull key = packKey(u, v); | |
| distCache.emplace(key, d); | |
| } | |
| inline void addEdge(int u, int v, ll w) { | |
| if (u == v) return; | |
| ull key = packKey(u, v); | |
| if (edgeSet.find(key) == edgeSet.end()) { | |
| edgeSet.insert(key); | |
| edges.emplace_back(u, v, w); | |
| } | |
| } | |
| void solveGroup(const vector<int>& S, int a) { | |
| if (S.size() <= 1) return; | |
| // Compute distances from anchor a to all in S (should be cached) | |
| ll maxd = -1; | |
| int b = a; | |
| vector<ll> da(S.size()); | |
| for (size_t i = 0; i < S.size(); ++i) { | |
| ll d = getDist(a, S[i]); | |
| da[i] = d; | |
| if (d > maxd) { | |
| maxd = d; | |
| b = S[i]; | |
| } | |
| } | |
| if ((int)S.size() == 2) { | |
| // Directly connect them | |
| int u = S[0], v = S[1]; | |
| ll w = getDist(u, v); | |
| addEdge(u, v, w); | |
| return; | |
| } | |
| // Distances from b to all in S (query/cached) | |
| vector<ll> db(S.size()); | |
| for (size_t i = 0; i < S.size(); ++i) { | |
| db[i] = getDist(b, S[i]); | |
| } | |
| ll D = getDist(a, b); | |
| // Identify on-path nodes and partition others by projection | |
| vector<pair<ll,int>> pathNodes; // (pos = da[v], v) for z=0 | |
| pathNodes.reserve(S.size()); | |
| // Map from path position (pos) to vertex id | |
| unordered_map<ll,int> pos2node; | |
| pos2node.reserve(S.size() * 2); | |
| // Groups attached to a path node (keyed by path node id) | |
| unordered_map<int, vector<int>> groups; | |
| for (size_t i = 0; i < S.size(); ++i) { | |
| ll z2 = da[i] + db[i] - D; | |
| // z = z2 / 2, guaranteed integer in tree metrics | |
| ll z = z2 / 2; | |
| if (z == 0) { | |
| ll pos = da[i]; // distance from a along the path | |
| pathNodes.emplace_back(pos, S[i]); | |
| } | |
| } | |
| sort(pathNodes.begin(), pathNodes.end()); | |
| pos2node.reserve(pathNodes.size()*2 + 1); | |
| for (auto &p : pathNodes) { | |
| pos2node[p.first] = p.second; | |
| } | |
| // Add edges along the path between a and b | |
| for (size_t i = 1; i < pathNodes.size(); ++i) { | |
| int u = pathNodes[i-1].second; | |
| int v = pathNodes[i].second; | |
| ll w = pathNodes[i].first - pathNodes[i-1].first; // difference in pos equals edge weight | |
| addEdge(u, v, w); | |
| } | |
| // Now group off-path nodes and set cached distances from projection node | |
| for (size_t i = 0; i < S.size(); ++i) { | |
| ll z2 = da[i] + db[i] - D; | |
| ll z = z2 / 2; | |
| if (z > 0) { | |
| ll pos = da[i] - z; | |
| auto it = pos2node.find(pos); | |
| if (it == pos2node.end()) { | |
| // Should not happen in a valid tree | |
| continue; | |
| } | |
| int proj = it->second; | |
| groups[proj].push_back(S[i]); | |
| // Cache distance from proj to this node as z | |
| setCachedDist(proj, S[i], z); | |
| } | |
| } | |
| // Recurse on each group with anchor at the projection node | |
| for (auto &kv : groups) { | |
| int proj = kv.first; | |
| vector<int> sub; | |
| sub.reserve(kv.second.size() + 1); | |
| sub.push_back(proj); | |
| for (int v : kv.second) sub.push_back(v); | |
| solveGroup(sub, proj); | |
| } | |
| } | |
| int main() { | |
| ios::sync_with_stdio(false); | |
| cin.tie(nullptr); | |
| int T; | |
| if (!(cin >> T)) return 0; | |
| while (T--) { | |
| if (!(cin >> n)) return 0; | |
| distCache.clear(); | |
| distCache.reserve(1 << 20); | |
| edgeSet.clear(); | |
| edgeSet.reserve((size_t)max(1, n - 1) * 2); | |
| edges.clear(); | |
| edges.reserve(max(1, n - 1)); | |
| if (n <= 1) { | |
| cout << "!" << endl; | |
| cout.flush(); | |
| continue; | |
| } | |
| int s = 1; | |
| // Query distances from s to all | |
| vector<int> allNodes(n); | |
| for (int i = 0; i < n; ++i) allNodes[i] = i + 1; | |
| for (int i = 2; i <= n; ++i) { | |
| getDist(s, i); | |
| } | |
| // Start recursive decomposition from anchor s over all nodes | |
| solveGroup(allNodes, s); | |
| // Output the edges | |
| cout << "!"; | |
| for (auto &e : edges) { | |
| int u, v; ll w; | |
| tie(u, v, w) = e; | |
| cout << " " << u << " " << v << " " << w; | |
| } | |
| cout << endl; | |
| cout.flush(); | |
| } | |
| return 0; | |
| } |