Download docker_space/frontier_cs_10/examples/grok4fastreasoning_3.cpp from JustinTX/shinka-backup: direct link, hf CLI and curl.
- Browser
- Download file 5.39 kB
-
https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/grok4fastreasoning_3.cpp
- Command line
-
hf download hf://JustinTX/shinka-backup/docker_space/frontier_cs_10/examples/grok4fastreasoning_3.cpp
-
curl -L -o grok4fastreasoning_3.cpp https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/grok4fastreasoning_3.cpp
5.39 kB
| using namespace std; | |
| int main() { | |
| ios::sync_with_stdio(false); | |
| cin.tie(nullptr); | |
| int T; | |
| cin >> T; | |
| for (int t = 0; t < T; ++t) { | |
| int n; | |
| cin >> n; | |
| if (n == 1) { | |
| cout << "!" << endl; | |
| cout.flush(); | |
| continue; | |
| } | |
| auto query = [&](int u, int v) -> long long { | |
| if (u == v) return 0; | |
| cout << "? " << u << " " << v << endl; | |
| cout.flush(); | |
| long long d; | |
| cin >> d; | |
| return d; | |
| }; | |
| auto get_dist = [&](int root, int nn) -> vector<long long> { | |
| vector<long long> d(nn + 1, 0); | |
| for (int v = 1; v <= nn; ++v) { | |
| if (v != root) { | |
| d[v] = query(root, v); | |
| } | |
| } | |
| return d; | |
| }; | |
| auto d1 = get_dist(1, n); | |
| int a = 1; | |
| for (int v = 1; v <= n; ++v) { | |
| if (d1[v] > d1[a]) a = v; | |
| } | |
| vector<long long> da = get_dist(a, n); | |
| int b = 1; | |
| for (int v = 1; v <= n; ++v) { | |
| if (da[v] > da[b]) b = v; | |
| } | |
| vector<long long> db = get_dist(b, n); | |
| long long dist_ab = da[b]; | |
| vector<pair<long long, int>> onpath_init; | |
| for (int v = 1; v <= n; ++v) { | |
| if (da[v] + db[v] == dist_ab) { | |
| onpath_init.emplace_back(da[v], v); | |
| } | |
| } | |
| sort(onpath_init.begin(), onpath_init.end()); | |
| vector<int> path; | |
| for (auto& p : onpath_init) path.push_back(p.second); | |
| vector<tuple<int, int, long long>> edges; | |
| for (size_t i = 0; i + 1 < onpath_init.size(); ++i) { | |
| int u = onpath_init[i].second; | |
| int v = onpath_init[i + 1].second; | |
| long long w = onpath_init[i + 1].first - onpath_init[i].first; | |
| edges.emplace_back(u, v, w); | |
| } | |
| map<long long, int> da_to_idx; | |
| for (size_t i = 0; i < onpath_init.size(); ++i) { | |
| da_to_idx[onpath_init[i].first] = i; | |
| } | |
| vector<bool> is_on_path(n + 1, false); | |
| for (int p : path) is_on_path[p] = true; | |
| vector<vector<int>> hangs(path.size()); | |
| for (int v = 1; v <= n; ++v) { | |
| if (is_on_path[v]) continue; | |
| long long cand = (da[v] + dist_ab - db[v]) / 2; | |
| auto it = da_to_idx.find(cand); | |
| if (it != da_to_idx.end()) { | |
| int id = it->second; | |
| hangs[id].push_back(v); | |
| } | |
| } | |
| auto reconstruct = [&](auto&& self, int rt, vector<int> S, function<long long(int)> get_dist_rt) -> void { | |
| if (S.empty()) return; | |
| int l = S[0]; | |
| long long maxd = get_dist_rt(l); | |
| for (int s : S) { | |
| long long dd = get_dist_rt(s); | |
| if (dd > maxd) { | |
| maxd = dd; | |
| l = s; | |
| } | |
| } | |
| vector<long long> dl(n + 1, -1); | |
| dl[l] = 0; | |
| dl[rt] = query(l, rt); | |
| for (int s : S) { | |
| if (s != l) { | |
| dl[s] = query(l, s); | |
| } | |
| } | |
| vector<pair<long long, int>> onpath; | |
| onpath.emplace_back(0LL, rt); | |
| for (int s : S) { | |
| if (get_dist_rt(s) + dl[s] == maxd) { | |
| onpath.emplace_back(get_dist_rt(s), s); | |
| } | |
| } | |
| sort(onpath.begin(), onpath.end()); | |
| for (size_t j = 0; j + 1 < onpath.size(); ++j) { | |
| int u = onpath[j].second; | |
| int v = onpath[j + 1].second; | |
| long long w = onpath[j + 1].first - onpath[j].first; | |
| edges.emplace_back(u, v, w); | |
| } | |
| vector<vector<int>> subhangs(onpath.size()); | |
| set<int> onpath_set; | |
| for (auto& p : onpath) onpath_set.insert(p.second); | |
| for (int s : S) { | |
| if (onpath_set.count(s)) continue; | |
| long long cand = (get_dist_rt(s) + maxd - dl[s]) / 2; | |
| auto it = lower_bound(onpath.begin(), onpath.end(), make_pair(cand, 0)); | |
| if (it != onpath.end() && it->first == cand) { | |
| size_t j = it - onpath.begin(); | |
| subhangs[j].push_back(s); | |
| } | |
| } | |
| for (size_t j = 0; j < onpath.size(); ++j) { | |
| int q = onpath[j].second; | |
| vector<int> subS = subhangs[j]; | |
| if (subS.empty()) continue; | |
| auto sub_get_dist = [get_dist_rt, q](int ss) -> long long { | |
| return get_dist_rt(ss) - get_dist_rt(q); | |
| }; | |
| self(self, q, subS, sub_get_dist); | |
| } | |
| }; | |
| for (size_t i = 0; i < path.size(); ++i) { | |
| int pi = path[i]; | |
| vector<int> Si = hangs[i]; | |
| if (!Si.empty()) { | |
| auto get_d = [&](int v) -> long long { | |
| return da[v] - da[pi]; | |
| }; | |
| reconstruct(reconstruct, pi, Si, get_d); | |
| } | |
| } | |
| cout << "!"; | |
| for (size_t i = 0; i < edges.size(); ++i) { | |
| auto [u, v, w] = edges[i]; | |
| cout << " " << u << " " << v << " " << w; | |
| } | |
| cout << endl; | |
| cout.flush(); | |
| } | |
| return 0; | |
| } |