Download docker_space/frontier_cs_10/examples/grok4fastreasoning_2.cpp from JustinTX/shinka-backup: direct link, hf CLI and curl.
- Browser
- Download file 3.39 kB
-
https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/grok4fastreasoning_2.cpp
- Command line
-
hf download hf://JustinTX/shinka-backup/docker_space/frontier_cs_10/examples/grok4fastreasoning_2.cpp
-
curl -L -o grok4fastreasoning_2.cpp https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/grok4fastreasoning_2.cpp
3.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; | |
| } | |
| vector<int> dist1(n + 1, 0); | |
| for (int i = 2; i <= n; ++i) { | |
| cout << "? 1 " << i << endl; | |
| cout.flush(); | |
| cin >> dist1[i]; | |
| } | |
| int two = 2; | |
| vector<int> dist2(n + 1, 0); | |
| for (int i = 1; i <= n; ++i) { | |
| if (i == two) continue; | |
| cout << "? " << two << " " << i << endl; | |
| cout.flush(); | |
| cin >> dist2[i]; | |
| } | |
| vector<int> path; | |
| for (int i = 1; i <= n; ++i) { | |
| if ((long long)dist1[i] + dist2[i] == dist1[two]) { | |
| path.push_back(i); | |
| } | |
| } | |
| sort(path.begin(), path.end(), [&](int x, int y) { | |
| return dist1[x] < dist1[y]; | |
| }); | |
| vector<tuple<int, int, int>> edges; | |
| for (size_t i = 0; i + 1 < path.size(); ++i) { | |
| int u = path[i], v = path[i + 1]; | |
| int w = dist1[v] - dist1[u]; | |
| edges.emplace_back(u, v, w); | |
| } | |
| vector<vector<int>> side_g(path.size()); | |
| set<int> onp(path.begin(), path.end()); | |
| for (int i = 1; i <= n; ++i) { | |
| if (onp.count(i)) continue; | |
| long long su = (long long)dist1[i] + dist1[two] - dist2[i]; | |
| assert(su % 2 == 0); | |
| int dep = su / 2; | |
| auto it = lower_bound(path.begin(), path.end(), dep, [&](int vv, int dd) { | |
| return dist1[vv] < dd; | |
| }); | |
| int j = it - path.begin(); | |
| if (j < (int)path.size() && dist1[path[j]] == dep) { | |
| side_g[j].push_back(i); | |
| } | |
| } | |
| function<void(int, vector<int>)> build_tree = [&](int root, vector<int> S) { | |
| if (S.empty()) return; | |
| sort(S.begin(), S.end(), [&](int a, int b) { | |
| return dist1[a] < dist1[b]; | |
| }); | |
| int min_ld = dist1[S[0]] - dist1[root]; | |
| vector<int> C; | |
| for (auto u : S) { | |
| if (dist1[u] - dist1[root] != min_ld) break; | |
| C.push_back(u); | |
| } | |
| vector<int> deeper; | |
| for (size_t i = C.size(); i < S.size(); ++i) deeper.push_back(S[i]); | |
| for (int c : C) { | |
| vector<int> sub_deeper; | |
| int exp_base = min_ld; | |
| for (int w : deeper) { | |
| cout << "? " << c << " " << w << endl; | |
| cout.flush(); | |
| int dw; | |
| cin >> dw; | |
| int expected = (dist1[w] - dist1[root]) - min_ld; | |
| if (dw == expected) { | |
| sub_deeper.push_back(w); | |
| } | |
| } | |
| edges.emplace_back(root, c, min_ld); | |
| build_tree(c, sub_deeper); | |
| } | |
| }; | |
| for (size_t j = 0; j < path.size(); ++j) { | |
| build_tree(path[j], side_g[j]); | |
| } | |
| cout << "!"; | |
| for (auto [u, v, w] : edges) { | |
| cout << " " << u << " " << v << " " << w; | |
| } | |
| cout << endl; | |
| cout.flush(); | |
| } | |
| return 0; | |
| } |