Download docker_space/frontier_cs_10/examples/gpt5.2_2.cpp from JustinTX/shinka-backup: direct link, hf CLI and curl.
- Browser
- Download file 5.23 kB
-
https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/gpt5.2_2.cpp
- Command line
-
hf download hf://JustinTX/shinka-backup/docker_space/frontier_cs_10/examples/gpt5.2_2.cpp
-
curl -L -o gpt5.2_2.cpp https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/gpt5.2_2.cpp
5.23 kB
| using namespace std; | |
| struct SplitMix64Hash { | |
| static uint64_t splitmix64(uint64_t x) { | |
| x += 0x9e3779b97f4a7c15ULL; | |
| x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL; | |
| x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL; | |
| return x ^ (x >> 31); | |
| } | |
| size_t operator()(uint64_t x) const { | |
| static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); | |
| return (size_t)splitmix64(x + FIXED_RANDOM); | |
| } | |
| }; | |
| static inline uint64_t pairKey(int u, int v) { | |
| if (u > v) std::swap(u, v); | |
| return (uint64_t(uint32_t(u)) << 32) | uint32_t(v); | |
| } | |
| struct Solver { | |
| int n = 0; | |
| long long queryCount = 0; | |
| unordered_map<uint64_t, long long, SplitMix64Hash> distCache; | |
| unordered_map<uint64_t, long long, SplitMix64Hash> edgeW; | |
| vector<tuple<int,int,long long>> edges; | |
| long long ask(int u, int v) { | |
| if (u == v) return 0; | |
| uint64_t k = pairKey(u, v); | |
| auto it = distCache.find(k); | |
| if (it != distCache.end()) return it->second; | |
| cout << "? " << u << " " << v << "\n" << std::flush; | |
| long long d; | |
| if (!(cin >> d)) exit(0); | |
| if (d < 0) exit(0); | |
| distCache.emplace(k, d); | |
| ++queryCount; | |
| return d; | |
| } | |
| void addEdge(int u, int v, long long w) { | |
| if (u == v) return; | |
| uint64_t k = pairKey(u, v); | |
| auto it = edgeW.find(k); | |
| if (it == edgeW.end()) { | |
| edgeW.emplace(k, w); | |
| edges.emplace_back(u, v, w); | |
| } else { | |
| // ignore if already exists; should match | |
| } | |
| } | |
| void processComponent(vector<int>&& comp, vector<vector<int>>& st) { | |
| int m = (int)comp.size(); | |
| if (m <= 1) return; | |
| int x = comp[0]; | |
| vector<long long> distX(m, 0); | |
| long long best = -1; | |
| int a = x; | |
| for (int i = 0; i < m; i++) { | |
| int v = comp[i]; | |
| long long d = (v == x) ? 0LL : ask(x, v); | |
| distX[i] = d; | |
| if (d > best) { | |
| best = d; | |
| a = v; | |
| } | |
| } | |
| vector<long long> distA(m, 0); | |
| best = -1; | |
| int b = a; | |
| for (int i = 0; i < m; i++) { | |
| int v = comp[i]; | |
| long long d = (v == a) ? 0LL : ask(a, v); | |
| distA[i] = d; | |
| if (d > best) { | |
| best = d; | |
| b = v; | |
| } | |
| } | |
| long long D = best; | |
| vector<long long> distB(m, 0); | |
| for (int i = 0; i < m; i++) { | |
| int v = comp[i]; | |
| distB[i] = (v == b) ? 0LL : ask(b, v); | |
| } | |
| vector<char> onPath(m, 0); | |
| vector<pair<long long,int>> path; | |
| path.reserve(m); | |
| for (int i = 0; i < m; i++) { | |
| if (distA[i] + distB[i] == D) { | |
| onPath[i] = 1; | |
| path.push_back({distA[i], comp[i]}); | |
| } | |
| } | |
| sort(path.begin(), path.end()); | |
| for (int i = 0; i + 1 < (int)path.size(); i++) { | |
| int u = path[i].second; | |
| int v = path[i + 1].second; | |
| long long w = path[i + 1].first - path[i].first; | |
| addEdge(u, v, w); | |
| } | |
| unordered_map<long long, int, SplitMix64Hash> posToIdx; | |
| posToIdx.reserve(path.size() * 2 + 1); | |
| for (int i = 0; i < (int)path.size(); i++) { | |
| posToIdx.emplace(path[i].first, i); | |
| } | |
| vector<vector<int>> groups(path.size()); | |
| for (int i = 0; i < m; i++) { | |
| if (onPath[i]) continue; | |
| long long xpos = (distA[i] + D - distB[i]) / 2; | |
| auto it = posToIdx.find(xpos); | |
| if (it == posToIdx.end()) continue; // should not happen | |
| groups[it->second].push_back(comp[i]); | |
| } | |
| for (int i = 0; i < (int)groups.size(); i++) { | |
| if (groups[i].empty()) continue; | |
| vector<int> nxt = std::move(groups[i]); | |
| nxt.push_back(path[i].second); | |
| st.push_back(std::move(nxt)); | |
| } | |
| } | |
| void solveOne() { | |
| cin >> n; | |
| edges.clear(); | |
| edgeW.clear(); | |
| distCache.clear(); | |
| queryCount = 0; | |
| edgeW.reserve((size_t)max(1, n * 2)); | |
| distCache.reserve((size_t)max(1, n * 40)); | |
| if (n <= 1) { | |
| cout << "!\n" << std::flush; | |
| return; | |
| } | |
| vector<int> init(n); | |
| iota(init.begin(), init.end(), 1); | |
| vector<vector<int>> st; | |
| st.reserve(n); | |
| st.push_back(std::move(init)); | |
| while (!st.empty()) { | |
| vector<int> comp = std::move(st.back()); | |
| st.pop_back(); | |
| processComponent(std::move(comp), st); | |
| } | |
| cout << "!"; | |
| // In rare cases due to duplicates we might have < n-1; still output what we have. | |
| for (auto &e : edges) { | |
| int u, v; | |
| long long w; | |
| tie(u, v, w) = e; | |
| cout << " " << u << " " << v << " " << w; | |
| } | |
| cout << "\n" << std::flush; | |
| } | |
| }; | |
| int main() { | |
| ios::sync_with_stdio(false); | |
| cin.tie(nullptr); | |
| int T; | |
| if (!(cin >> T)) return 0; | |
| Solver solver; | |
| while (T--) solver.solveOne(); | |
| return 0; | |
| } |