Download docker_space/frontier_cs_10/examples/gpt5_high.cpp from JustinTX/shinka-backup: direct link, hf CLI and curl.
- Browser
- Download file 5.99 kB
-
https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/gpt5_high.cpp
- Command line
-
hf download hf://JustinTX/shinka-backup/docker_space/frontier_cs_10/examples/gpt5_high.cpp
-
curl -L -o gpt5_high.cpp https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_10/examples/gpt5_high.cpp
5.99 kB
| using namespace std; | |
| struct FastScanner { | |
| static inline int gc() { | |
| return getchar(); | |
| } | |
| bool readLongLong(long long &out) { | |
| int c = gc(); | |
| while (c != EOF && (c != '-' && (c < '0' || c > '9'))) c = gc(); | |
| if (c == EOF) return false; | |
| int sign = 1; | |
| if (c == '-') { sign = -1; c = gc(); } | |
| long long x = 0; | |
| while (c >= '0' && c <= '9') { | |
| x = x * 10 + (c - '0'); | |
| c = gc(); | |
| } | |
| out = x * sign; | |
| return true; | |
| } | |
| bool readInt(int &out) { | |
| long long tmp; | |
| if (!readLongLong(tmp)) return false; | |
| out = (int)tmp; | |
| return true; | |
| } | |
| }; | |
| struct DistMatrix { | |
| int n; | |
| vector<long long> tri; // upper triangular (i<j) stored row-wise | |
| vector<long long> offset; // offset for i: starting index in tri for pairs (i, j>i) | |
| DistMatrix() : n(0) {} | |
| DistMatrix(int _n) { init(_n); } | |
| void init(int _n) { | |
| n = _n; | |
| long long m = 1LL * n * (n - 1) / 2; | |
| tri.assign((size_t)m, 0); | |
| offset.assign(n + 2, 0); | |
| // offset[i] = sum_{k=1}^{i-1} (n - k) = (i-1)*n - (i-1)*i/2 | |
| for (int i = 1; i <= n; ++i) { | |
| offset[i] = 1LL * (i - 1) * n - 1LL * (i - 1) * i / 2; | |
| } | |
| } | |
| inline long long &atPairIdx(int i, int j) { // i<j | |
| return tri[(size_t)(offset[i] + (j - i - 1))]; | |
| } | |
| inline long long get(int i, int j) const { | |
| if (i == j) return 0; | |
| if (i < j) { | |
| return tri[(size_t)(offset[i] + (j - i - 1))]; | |
| } else { | |
| return tri[(size_t)(offset[j] + (i - j - 1))]; | |
| } | |
| } | |
| }; | |
| int N; | |
| DistMatrix D; | |
| vector<tuple<int,int,long long>> edges; | |
| void reconstruct(const vector<int> &S) { | |
| if (S.size() <= 1) return; | |
| // find diameter endpoints within S using two-sweep | |
| int s0 = S[0]; | |
| int t = s0; | |
| long long best = -1; | |
| for (int x : S) { | |
| long long dv = D.get(s0, x); | |
| if (dv > best) { best = dv; t = x; } | |
| } | |
| int u = t; | |
| best = -1; | |
| for (int x : S) { | |
| long long dv = D.get(t, x); | |
| if (dv > best) { best = dv; u = x; } | |
| } | |
| int a = u, b = t; | |
| long long Sab = D.get(a, b); | |
| // collect nodes on path from a to b | |
| vector<int> pathNodes; | |
| pathNodes.reserve(S.size()); | |
| for (int x : S) { | |
| if (D.get(a, x) + D.get(x, b) == Sab) pathNodes.push_back(x); | |
| } | |
| sort(pathNodes.begin(), pathNodes.end(), [&](int x, int y){ | |
| return D.get(a, x) < D.get(a, y); | |
| }); | |
| // add edges along the path | |
| for (size_t i = 0; i + 1 < pathNodes.size(); ++i) { | |
| int u1 = pathNodes[i], v1 = pathNodes[i+1]; | |
| long long w = D.get(a, v1) - D.get(a, u1); | |
| edges.emplace_back(u1, v1, w); | |
| } | |
| // prepare mapping: node -> index in path, and distances from a along path | |
| vector<int> idxInPath(N + 1, -1); | |
| vector<long long> distAPath(pathNodes.size()); | |
| for (size_t i = 0; i < pathNodes.size(); ++i) { | |
| idxInPath[pathNodes[i]] = (int)i; | |
| distAPath[i] = D.get(a, pathNodes[i]); | |
| } | |
| // groups for recursion: for each path index, collect nodes not on path that project to that node | |
| vector<vector<int>> groups(pathNodes.size()); | |
| vector<char> inPath(N + 1, 0); | |
| for (int p : pathNodes) inPath[p] = 1; | |
| for (int v : S) if (!inPath[v]) { | |
| long long da = D.get(a, v), db = D.get(b, v); | |
| long long delta2 = da + db - Sab; // 2*delta | |
| long long delta = delta2 / 2; | |
| long long xdist = da - delta; // distance from a to projection on path | |
| // binary search xdist in distAPath | |
| auto it = lower_bound(distAPath.begin(), distAPath.end(), xdist); | |
| if (it == distAPath.end() || *it != xdist) { | |
| // theoretically should not happen in a valid tree metric | |
| // but if it does, we skip to avoid crash | |
| continue; | |
| } | |
| int pos = (int)(it - distAPath.begin()); | |
| groups[pos].push_back(v); | |
| } | |
| // recurse on each group | |
| for (size_t i = 0; i < groups.size(); ++i) { | |
| if (!groups[i].empty()) { | |
| vector<int> subS; | |
| subS.reserve(groups[i].size() + 1); | |
| subS.push_back(pathNodes[i]); | |
| for (int v : groups[i]) subS.push_back(v); | |
| reconstruct(subS); | |
| } | |
| } | |
| } | |
| int main() { | |
| ios::sync_with_stdio(false); | |
| cin.tie(nullptr); | |
| FastScanner fs; | |
| int T; | |
| { | |
| int tmp; | |
| if (!fs.readInt(tmp)) return 0; | |
| T = tmp; | |
| } | |
| for (int tc = 0; tc < T; ++tc) { | |
| int n; | |
| { | |
| int tmp; | |
| fs.readInt(tmp); | |
| n = tmp; | |
| } | |
| N = n; | |
| D.init(n); | |
| long long m = 1LL * n * (n - 1) / 2; | |
| for (int i = 1; i <= n - 1; ++i) { | |
| for (int j = i + 1; j <= n; ++j) { | |
| long long val; | |
| fs.readLongLong(val); | |
| D.atPairIdx(i, j) = val; | |
| } | |
| } | |
| edges.clear(); | |
| edges.reserve((size_t)max(0, n - 1)); | |
| vector<int> all(n); | |
| for (int i = 0; i < n; ++i) all[i] = i + 1; | |
| reconstruct(all); | |
| cout << "!"; | |
| // If by some chance we have more than n-1 due to duplicates, we can trim by using a map | |
| if ((int)edges.size() != n - 1) { | |
| // Deduplicate just in case | |
| map<pair<int,int>, long long> mp; | |
| for (auto &e : edges) { | |
| int u, v; long long w; | |
| tie(u, v, w) = e; | |
| if (u > v) swap(u, v); | |
| mp[{u, v}] = w; | |
| } | |
| edges.clear(); | |
| edges.reserve(mp.size()); | |
| for (auto &kv : mp) { | |
| edges.emplace_back(kv.first.first, kv.first.second, kv.second); | |
| } | |
| } | |
| for (auto &e : edges) { | |
| int u, v; long long w; | |
| tie(u, v, w) = e; | |
| cout << " " << u << " " << v << " " << w; | |
| } | |
| cout << "\n"; | |
| } | |
| return 0; | |
| } |