Download docker_space/frontier_cs_1/examples/gpt5_high_1.cpp from JustinTX/shinka-backup: direct link, hf CLI and curl.
- Browser
- Download file 16.9 kB
-
https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_1/examples/gpt5_high_1.cpp
- Command line
-
hf download hf://JustinTX/shinka-backup/docker_space/frontier_cs_1/examples/gpt5_high_1.cpp
-
curl -L -o gpt5_high_1.cpp https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_1/examples/gpt5_high_1.cpp
16.9 kB
| using namespace std; | |
| struct Item { | |
| string name; | |
| long long q, v, m, l; | |
| int idx; | |
| }; | |
| struct Parser { | |
| string s; | |
| size_t pos = 0; | |
| Parser(const string& str) : s(str), pos(0) {} | |
| void skipWS() { | |
| while (pos < s.size() && isspace((unsigned char)s[pos])) pos++; | |
| } | |
| bool match(char c) { | |
| skipWS(); | |
| if (pos < s.size() && s[pos] == c) { | |
| pos++; | |
| return true; | |
| } | |
| return false; | |
| } | |
| void expect(char c) { | |
| skipWS(); | |
| if (pos >= s.size() || s[pos] != c) { | |
| // Fallback: try to progress to avoid infinite loop | |
| // but in contest, just ensure format is correct. | |
| // For safety, move pos to end. | |
| pos = s.size(); | |
| return; | |
| } | |
| pos++; | |
| } | |
| string parseString() { | |
| skipWS(); | |
| string res; | |
| if (pos < s.size() && s[pos] == '"') { | |
| pos++; | |
| while (pos < s.size()) { | |
| char c = s[pos++]; | |
| if (c == '\\') { | |
| if (pos < s.size()) { | |
| char next = s[pos++]; | |
| // Handle simple escapes | |
| if (next == '"' || next == '\\' || next == '/') res.push_back(next); | |
| else if (next == 'b') res.push_back('\b'); | |
| else if (next == 'f') res.push_back('\f'); | |
| else if (next == 'n') res.push_back('\n'); | |
| else if (next == 'r') res.push_back('\r'); | |
| else if (next == 't') res.push_back('\t'); | |
| else res.push_back(next); | |
| } | |
| } else if (c == '"') { | |
| break; | |
| } else { | |
| res.push_back(c); | |
| } | |
| } | |
| } | |
| return res; | |
| } | |
| long long parseInt() { | |
| skipWS(); | |
| bool neg = false; | |
| if (pos < s.size() && (s[pos] == '-' || s[pos] == '+')) { | |
| neg = (s[pos] == '-'); | |
| pos++; | |
| } | |
| long long val = 0; | |
| while (pos < s.size() && isdigit((unsigned char)s[pos])) { | |
| val = val * 10 + (s[pos] - '0'); | |
| pos++; | |
| } | |
| return neg ? -val : val; | |
| } | |
| vector<Item> parse() { | |
| vector<Item> items; | |
| expect('{'); | |
| while (true) { | |
| skipWS(); | |
| if (pos >= s.size()) break; | |
| if (s[pos] == '}') { pos++; break; } | |
| string key = parseString(); | |
| expect(':'); | |
| // parse array [q, v, m, l] | |
| expect('['); | |
| long long q = parseInt(); expect(','); | |
| long long v = parseInt(); expect(','); | |
| long long m = parseInt(); expect(','); | |
| long long l = parseInt(); | |
| expect(']'); | |
| Item it; | |
| it.name = key; it.q = q; it.v = v; it.m = m; it.l = l; | |
| it.idx = (int)items.size(); | |
| items.push_back(it); | |
| skipWS(); | |
| if (pos < s.size() && s[pos] == ',') pos++; | |
| } | |
| return items; | |
| } | |
| }; | |
| struct Solution { | |
| vector<long long> cnt; | |
| long long val=0, usedM=0, usedL=0; | |
| }; | |
| static const long long CAP_M = 20000000LL; // mg | |
| static const long long CAP_L = 25000000LL; // uL | |
| struct HeuristicSolver { | |
| vector<Item> items; | |
| int n; | |
| vector<long long> qLim; | |
| HeuristicSolver(const vector<Item>& its) : items(its) { | |
| n = (int)items.size(); | |
| qLim.resize(n); | |
| for (int i = 0; i < n; ++i) { | |
| long long qm = items[i].m > 0 ? (CAP_M / items[i].m) : 0; | |
| long long ql = items[i].l > 0 ? (CAP_L / items[i].l) : 0; | |
| qLim[i] = min(items[i].q, min(qm, ql)); | |
| } | |
| } | |
| Solution evaluate(const vector<long long>& cnt) { | |
| Solution s; | |
| s.cnt = cnt; | |
| long long M=0, L=0, V=0; | |
| for (int i = 0; i < n; ++i) { | |
| long long c = cnt[i]; | |
| if (c < 0) { s.val = -1; return s; } | |
| if (c > qLim[i]) { s.val = -1; return s; } | |
| V += c * items[i].v; | |
| M += c * items[i].m; | |
| L += c * items[i].l; | |
| } | |
| if (M > CAP_M || L > CAP_L) { s.val = -1; return s; } | |
| s.val = V; s.usedM = M; s.usedL = L; | |
| return s; | |
| } | |
| vector<int> sorted_by_ratio(double alpha) { | |
| vector<pair<double,int>> arr; | |
| arr.reserve(n); | |
| for (int i = 0; i < n; ++i) { | |
| double cm = (double)items[i].m / (double)CAP_M; | |
| double cl = (double)items[i].l / (double)CAP_L; | |
| double denom = alpha * cm + (1.0 - alpha) * cl; | |
| double ratio = (denom > 0) ? ( (double)items[i].v / denom ) : 1e300; | |
| arr.emplace_back(ratio, i); | |
| } | |
| sort(arr.begin(), arr.end(), [&](auto& a, auto& b){ | |
| if (a.first != b.first) return a.first > b.first; | |
| // tie-breakers: higher value, lower mass+volume | |
| const Item &ia = items[a.second], &ib = items[b.second]; | |
| if (ia.v != ib.v) return ia.v > ib.v; | |
| long long sa = ia.m + ia.l, sb = ib.m + ib.l; | |
| return sa < sb; | |
| }); | |
| vector<int> order; order.reserve(n); | |
| for (auto &p : arr) order.push_back(p.second); | |
| return order; | |
| } | |
| vector<int> sorted_by_maxnorm() { | |
| vector<pair<double,int>> arr; | |
| arr.reserve(n); | |
| for (int i = 0; i < n; ++i) { | |
| double cnm = (double)items[i].m / (double)CAP_M; | |
| double cnl = (double)items[i].l / (double)CAP_L; | |
| double denom = max(cnm, cnl); | |
| double ratio = (denom > 0) ? ((double)items[i].v / denom) : 1e300; | |
| arr.emplace_back(ratio, i); | |
| } | |
| sort(arr.begin(), arr.end(), [&](auto& a, auto& b){ | |
| if (a.first != b.first) return a.first > b.first; | |
| const Item &ia = items[a.second], &ib = items[b.second]; | |
| if (ia.v != ib.v) return ia.v > ib.v; | |
| long long sa = ia.m + ia.l, sb = ib.m + ib.l; | |
| return sa < sb; | |
| }); | |
| vector<int> order; order.reserve(n); | |
| for (auto &p : arr) order.push_back(p.second); | |
| return order; | |
| } | |
| vector<long long> fill_sorted_order(const vector<int>& order) { | |
| vector<long long> cnt(n, 0); | |
| long long RM = CAP_M, RL = CAP_L; | |
| for (int idx : order) { | |
| if (qLim[idx] <= 0) continue; | |
| long long cm = items[idx].m, cl = items[idx].l; | |
| if (cm == 0 || cl == 0) continue; // should not happen | |
| long long canM = RM / cm; | |
| long long canL = RL / cl; | |
| long long add = min(qLim[idx] - cnt[idx], min(canM, canL)); | |
| if (add <= 0) continue; | |
| cnt[idx] += add; | |
| RM -= add * cm; | |
| RL -= add * cl; | |
| } | |
| return cnt; | |
| } | |
| vector<long long> fill_incremental_static_ratio(double alpha, vector<long long> startCnt = {}) { | |
| vector<long long> cnt = startCnt.empty() ? vector<long long>(n, 0) : startCnt; | |
| long long usedM = 0, usedL = 0; | |
| if (!startCnt.empty()) { | |
| for (int i = 0; i < n; ++i) { | |
| usedM += cnt[i] * items[i].m; | |
| usedL += cnt[i] * items[i].l; | |
| } | |
| } | |
| long long RM = CAP_M - usedM, RL = CAP_L - usedL; | |
| if (RM < 0 || RL < 0) return cnt; | |
| // Precompute static scores | |
| vector<double> score(n, -1e300); | |
| for (int i = 0; i < n; ++i) { | |
| double cm = (double)items[i].m / (double)CAP_M; | |
| double cl = (double)items[i].l / (double)CAP_L; | |
| double denom = alpha * cm + (1.0 - alpha) * cl; | |
| score[i] = (denom > 0) ? ((double)items[i].v / denom) : 1e300; | |
| } | |
| while (true) { | |
| int best = -1; | |
| double bestScore = -1e300; | |
| for (int i = 0; i < n; ++i) { | |
| if (cnt[i] >= qLim[i]) continue; | |
| if (items[i].m <= RM && items[i].l <= RL) { | |
| double sc = score[i]; | |
| if (sc > bestScore) { | |
| bestScore = sc; best = i; | |
| } | |
| } | |
| } | |
| if (best == -1) break; | |
| cnt[best] += 1; | |
| RM -= items[best].m; | |
| RL -= items[best].l; | |
| } | |
| return cnt; | |
| } | |
| vector<long long> fill_incremental_dynamic_ratio(vector<long long> startCnt = {}) { | |
| vector<long long> cnt = startCnt.empty() ? vector<long long>(n, 0) : startCnt; | |
| long long usedM = 0, usedL = 0; | |
| if (!startCnt.empty()) { | |
| for (int i = 0; i < n; ++i) { | |
| usedM += cnt[i] * items[i].m; | |
| usedL += cnt[i] * items[i].l; | |
| } | |
| } | |
| long long RM = CAP_M - usedM, RL = CAP_L - usedL; | |
| if (RM < 0 || RL < 0) return cnt; | |
| while (true) { | |
| int best = -1; | |
| double bestScore = -1e300; | |
| double wm = (RM > 0) ? (1.0 / (double)RM) : 1e300; | |
| double wl = (RL > 0) ? (1.0 / (double)RL) : 1e300; | |
| for (int i = 0; i < n; ++i) { | |
| if (cnt[i] >= qLim[i]) continue; | |
| if (items[i].m <= RM && items[i].l <= RL) { | |
| double denom = items[i].m * wm + items[i].l * wl; | |
| double sc = denom > 0 ? ((double)items[i].v / denom) : 1e300; | |
| if (sc > bestScore) { | |
| bestScore = sc; best = i; | |
| } | |
| } | |
| } | |
| if (best == -1) break; | |
| cnt[best] += 1; | |
| RM -= items[best].m; | |
| RL -= items[best].l; | |
| } | |
| return cnt; | |
| } | |
| Solution best_of_candidates(const vector<vector<long long>>& cands) { | |
| Solution best; | |
| best.val = -1; | |
| for (auto &cnt : cands) { | |
| Solution s = evaluate(cnt); | |
| if (s.val > best.val) best = s; | |
| } | |
| if (best.val < 0) { | |
| // fallback to empty | |
| best = evaluate(vector<long long>(n,0)); | |
| } | |
| return best; | |
| } | |
| vector<long long> greedy_refill(vector<long long> cnt, long long RM, long long RL, double alpha) { | |
| // refill incrementally with static ratio alpha | |
| // ensure counts satisfy qLim and capacity | |
| // We'll select best each step | |
| vector<double> score(n, -1e300); | |
| for (int i = 0; i < n; ++i) { | |
| double cm = (double)items[i].m / (double)CAP_M; | |
| double cl = (double)items[i].l / (double)CAP_L; | |
| double denom = alpha * cm + (1.0 - alpha) * cl; | |
| score[i] = (denom > 0) ? ((double)items[i].v / denom) : 1e300; | |
| } | |
| while (true) { | |
| int best = -1; | |
| double bestScore = -1e300; | |
| for (int i = 0; i < n; ++i) { | |
| if (cnt[i] >= qLim[i]) continue; | |
| if (items[i].m <= RM && items[i].l <= RL) { | |
| double sc = score[i]; | |
| if (sc > bestScore) { | |
| bestScore = sc; best = i; | |
| } | |
| } | |
| } | |
| if (best == -1) break; | |
| cnt[best] += 1; | |
| RM -= items[best].m; | |
| RL -= items[best].l; | |
| } | |
| return cnt; | |
| } | |
| Solution local_improve(Solution start) { | |
| vector<long long> cnt = start.cnt; | |
| long long usedM = start.usedM, usedL = start.usedL; | |
| long long bestVal = start.val; | |
| int maxPasses = 2; // keep small for time | |
| int Kremove = 8; | |
| for (int pass = 0; pass < maxPasses; ++pass) { | |
| bool improved = false; | |
| // prioritize items currently included | |
| vector<int> idxs(n); | |
| iota(idxs.begin(), idxs.end(), 0); | |
| sort(idxs.begin(), idxs.end(), [&](int a, int b){ | |
| if (cnt[a] != cnt[b]) return cnt[a] > cnt[b]; | |
| return items[a].v > items[b].v; | |
| }); | |
| for (int ii = 0; ii < n; ++ii) { | |
| int i = idxs[ii]; | |
| if (cnt[i] <= 0) continue; | |
| int maxK = (int)min<long long>(cnt[i], Kremove); | |
| for (int k = 1; k <= maxK; ++k) { | |
| vector<long long> tmp = cnt; | |
| tmp[i] -= k; | |
| long long RM = usedM + k * items[i].m; | |
| long long RL = usedL + k * items[i].l; | |
| // Now refill | |
| vector<double> alphas = {0.0, 0.5, 1.0}; | |
| long long bestLocalVal = -1; | |
| vector<long long> bestLocalCnt; | |
| for (double a : alphas) { | |
| vector<long long> filled = greedy_refill(tmp, RM, RL, a); | |
| Solution s = evaluate(filled); | |
| if (s.val > bestLocalVal) { | |
| bestLocalVal = s.val; | |
| bestLocalCnt = move(filled); | |
| } | |
| } | |
| if (bestLocalVal > bestVal) { | |
| // accept | |
| Solution s = evaluate(bestLocalCnt); | |
| cnt = move(bestLocalCnt); | |
| usedM = s.usedM; usedL = s.usedL; bestVal = s.val; | |
| improved = true; | |
| break; | |
| } | |
| } | |
| if (improved) break; | |
| } | |
| if (!improved) break; | |
| } | |
| Solution res = evaluate(cnt); | |
| return res; | |
| } | |
| Solution solve() { | |
| vector<vector<long long>> candidates; | |
| candidates.reserve(64); | |
| // alpha-based greedy | |
| vector<double> alphas = {0.0, 0.1, 0.2, 0.25, 0.3, 0.4, 0.5, 0.6, 0.7, 0.75, 0.8, 0.9, 1.0}; | |
| for (double a : alphas) { | |
| auto order = sorted_by_ratio(a); | |
| candidates.push_back(fill_sorted_order(order)); | |
| candidates.push_back(fill_incremental_static_ratio(a)); | |
| } | |
| // max-norm | |
| auto ord_max = sorted_by_maxnorm(); | |
| candidates.push_back(fill_sorted_order(ord_max)); | |
| // dynamic incremental | |
| candidates.push_back(fill_incremental_dynamic_ratio()); | |
| // Additional heuristics: sort by value desc | |
| { | |
| vector<int> order(n); | |
| iota(order.begin(), order.end(), 0); | |
| sort(order.begin(), order.end(), [&](int i, int j){ | |
| if (items[i].v != items[j].v) return items[i].v > items[j].v; | |
| long long si = items[i].m + items[i].l, sj = items[j].m + items[j].l; | |
| return si < sj; | |
| }); | |
| candidates.push_back(fill_sorted_order(order)); | |
| } | |
| // sort by mass efficiency v/m | |
| { | |
| vector<pair<double,int>> arr; | |
| for (int i=0;i<n;++i){ | |
| double eff = (items[i].m>0)? (double)items[i].v / (double)items[i].m : 1e300; | |
| arr.emplace_back(eff,i); | |
| } | |
| sort(arr.begin(), arr.end(), [&](auto&a, auto&b){ | |
| if (a.first != b.first) return a.first > b.first; | |
| return items[a.second].v > items[b.second].v; | |
| }); | |
| vector<int> order; order.reserve(n); | |
| for (auto &p:arr) order.push_back(p.second); | |
| candidates.push_back(fill_sorted_order(order)); | |
| } | |
| // sort by volume efficiency v/l | |
| { | |
| vector<pair<double,int>> arr; | |
| for (int i=0;i<n;++i){ | |
| double eff = (items[i].l>0)? (double)items[i].v / (double)items[i].l : 1e300; | |
| arr.emplace_back(eff,i); | |
| } | |
| sort(arr.begin(), arr.end(), [&](auto&a, auto&b){ | |
| if (a.first != b.first) return a.first > b.first; | |
| return items[a.second].v > items[b.second].v; | |
| }); | |
| vector<int> order; order.reserve(n); | |
| for (auto &p:arr) order.push_back(p.second); | |
| candidates.push_back(fill_sorted_order(order)); | |
| } | |
| Solution best = best_of_candidates(candidates); | |
| // Local improvement | |
| best = local_improve(best); | |
| return best; | |
| } | |
| }; | |
| int main() { | |
| ios::sync_with_stdio(false); | |
| cin.tie(nullptr); | |
| string input; | |
| { | |
| ostringstream oss; | |
| oss << cin.rdbuf(); | |
| input = oss.str(); | |
| } | |
| Parser parser(input); | |
| vector<Item> items = parser.parse(); | |
| // Ensure exactly 12 categories; if not, proceed anyway | |
| HeuristicSolver solver(items); | |
| Solution best = solver.solve(); | |
| // Output JSON with original keys and counts | |
| cout << "{\n"; | |
| for (size_t i = 0; i < items.size(); ++i) { | |
| cout << " \"" << items[i].name << "\": " << (best.cnt.size() > i ? best.cnt[i] : 0); | |
| if (i + 1 < items.size()) cout << ",\n"; | |
| else cout << "\n"; | |
| } | |
| cout << "}\n"; | |
| return 0; | |
| } |