Download docker_space/frontier_cs_1/solution.cpp from JustinTX/shinka-backup: direct link, hf CLI and curl.
- Browser
- Download file 24.4 kB
-
https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_1/solution.cpp
- Command line
-
hf download hf://JustinTX/shinka-backup/docker_space/frontier_cs_1/solution.cpp
-
curl -L -o solution.cpp https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_1/solution.cpp
24.4 kB
| using namespace std; | |
| struct Item { | |
| string name; | |
| int q; | |
| long long v, m, l; | |
| }; | |
| static inline void skip_ws(const string& s, size_t& i) { | |
| while (i < s.size() && isspace((unsigned char)s[i])) i++; | |
| } | |
| static string parse_string(const string& s, size_t& i) { | |
| skip_ws(s, i); | |
| if (i >= s.size() || s[i] != '"') return ""; | |
| i++; | |
| string out; | |
| while (i < s.size()) { | |
| char c = s[i++]; | |
| if (c == '"') break; | |
| if (c == '\\') { | |
| if (i < s.size()) { | |
| char e = s[i++]; | |
| out.push_back(e); | |
| } | |
| } else out.push_back(c); | |
| } | |
| return out; | |
| } | |
| static long long parse_int(const string& s, size_t& i) { | |
| skip_ws(s, i); | |
| bool neg = false; | |
| if (i < s.size() && s[i] == '-') { neg = true; i++; } | |
| long long x = 0; | |
| while (i < s.size() && isdigit((unsigned char)s[i])) { | |
| x = x * 10 + (s[i] - '0'); | |
| i++; | |
| } | |
| return neg ? -x : x; | |
| } | |
| struct Solution { | |
| array<int,12> x{}; | |
| long long value = 0; | |
| long long usedM = 0, usedL = 0; | |
| }; | |
| static inline long long compute_value(const vector<Item>& items, const array<int,12>& x) { | |
| long long val = 0; | |
| for (int i = 0; i < 12; i++) val += (long long)x[i] * items[i].v; | |
| return val; | |
| } | |
| static inline pair<long long,long long> compute_used(const vector<Item>& items, const array<int,12>& x) { | |
| __int128 um = 0, ul = 0; | |
| for (int i = 0; i < 12; i++) { | |
| um += (__int128)x[i] * items[i].m; | |
| ul += (__int128)x[i] * items[i].l; | |
| } | |
| return {(long long)um, (long long)ul}; | |
| } | |
| // One-at-a-time greedy with dynamic residual scoring | |
| static Solution greedy_one_at_a_time(const vector<Item>& items, long long M, long long L, int mode, double gamma) { | |
| Solution sol; | |
| long long remM = M, remL = L; | |
| int n = (int)items.size(); | |
| while (true) { | |
| int best = -1; | |
| long double bestScore = -1.0L; | |
| for (int i = 0; i < n; i++) { | |
| if (sol.x[i] >= items[i].q) continue; | |
| if (items[i].m > remM || items[i].l > remL) continue; | |
| long double denom = 0.0L; | |
| if (mode == 0) { | |
| // residual sum | |
| denom = (long double)items[i].m / (long double)remM + (long double)items[i].l / (long double)remL; | |
| } else if (mode == 1) { | |
| // residual max | |
| long double a = (long double)items[i].m / (long double)remM; | |
| long double b = (long double)items[i].l / (long double)remL; | |
| denom = (a > b ? a : b); | |
| } else if (mode == 2) { | |
| // weighted residual | |
| denom = gamma * ((long double)items[i].m / (long double)remM) + (1.0 - gamma) * ((long double)items[i].l / (long double)remL); | |
| } else if (mode == 3) { | |
| // weighted constant | |
| denom = gamma * ((long double)items[i].m / (long double)M) + (1.0 - gamma) * ((long double)items[i].l / (long double)L); | |
| } | |
| if (denom <= 0.0L) continue; | |
| long double score = (long double)items[i].v / denom; | |
| if (score > bestScore) { | |
| bestScore = score; | |
| best = i; | |
| } | |
| } | |
| if (best == -1) break; | |
| sol.x[best]++; | |
| remM -= items[best].m; | |
| remL -= items[best].l; | |
| sol.value += items[best].v; | |
| } | |
| sol.usedM = M - remM; | |
| sol.usedL = L - remL; | |
| return sol; | |
| } | |
| static Solution greedy(const vector<Item>& items, long long M, long long L, long double alphaM, long double alphaL) { | |
| vector<int> idx(12); | |
| iota(idx.begin(), idx.end(), 0); | |
| vector<long double> score(12, 0); | |
| for (int i = 0; i < 12; i++) { | |
| long double denom = alphaM * (long double)items[i].m + alphaL * (long double)items[i].l; | |
| if (denom <= 0) score[i] = 0; | |
| else score[i] = (long double)items[i].v / denom; | |
| } | |
| stable_sort(idx.begin(), idx.end(), [&](int a, int b){ | |
| if (score[a] != score[b]) return score[a] > score[b]; | |
| return items[a].v > items[b].v; | |
| }); | |
| Solution sol; | |
| long long remM = M, remL = L; | |
| for (int id : idx) { | |
| if (items[id].m > remM || items[id].l > remL) continue; | |
| long long byM = remM / items[id].m; | |
| long long byL = remL / items[id].l; | |
| long long take = min<long long>(items[id].q, min(byM, byL)); | |
| sol.x[id] = (int)take; | |
| remM -= take * items[id].m; | |
| remL -= take * items[id].l; | |
| sol.value += take * items[id].v; | |
| sol.usedM += take * items[id].m; | |
| sol.usedL += take * items[id].l; | |
| } | |
| return sol; | |
| } | |
| struct WeightRun { | |
| long long p, q; | |
| bool volCoeff; | |
| }; | |
| struct BeamState { | |
| array<int,12> x{}; | |
| long long remM = 0, remL = 0; | |
| long long val = 0; | |
| long double ub = 0; | |
| }; | |
| static long double fractional_bound( | |
| const vector<Item>& items, | |
| const vector<int>& order, | |
| int pos, | |
| long long remM, long long remL, | |
| long long M, long long L, | |
| long long wM1, long long wL1 | |
| ) { | |
| __int128 remW128 = (__int128)remM * wM1 + (__int128)remL * wL1; | |
| long long remW = (remW128 > (__int128)LLONG_MAX ? LLONG_MAX : (long long)remW128); | |
| long double add = 0.0L; | |
| for (int k = pos; k < (int)order.size(); k++) { | |
| int i = order[k]; | |
| long long wi; | |
| { | |
| __int128 w128 = (__int128)items[i].m * wM1 + (__int128)items[i].l * wL1; | |
| if (w128 <= 0) continue; | |
| wi = (w128 > (__int128)LLONG_MAX ? LLONG_MAX : (long long)w128); | |
| } | |
| if (wi <= 0) continue; | |
| long long capByM = (items[i].m == 0 ? (long long)items[i].q : remM / items[i].m); | |
| long long capByL = (items[i].l == 0 ? (long long)items[i].q : remL / items[i].l); | |
| long long avail = min<long long>(items[i].q, min(capByM, capByL)); | |
| if (avail <= 0) continue; | |
| if (remW <= 0) break; | |
| long long take = min(avail, remW / wi); | |
| if (take > 0) { | |
| add += (long double)take * (long double)items[i].v; | |
| remW -= take * wi; | |
| remM -= take * items[i].m; | |
| remL -= take * items[i].l; | |
| } | |
| if (take < avail && remW > 0) { | |
| add += (long double)remW * ((long double)items[i].v / (long double)wi); | |
| break; | |
| } | |
| } | |
| return add; | |
| } | |
| static Solution beam_search( | |
| const vector<Item>& items, | |
| long long M, long long L, | |
| const WeightRun& wr, | |
| int BEAM_W | |
| ) { | |
| long long wM1, wL1; | |
| if (wr.volCoeff) { | |
| wM1 = L * wr.q; | |
| wL1 = M * wr.p; | |
| } else { | |
| wM1 = L * wr.p; | |
| wL1 = M * wr.q; | |
| } | |
| vector<int> order(12); | |
| iota(order.begin(), order.end(), 0); | |
| vector<long double> dens(12, 0.0L); | |
| for (int i = 0; i < 12; i++) { | |
| __int128 w128 = (__int128)items[i].m * wM1 + (__int128)items[i].l * wL1; | |
| long double wi = (w128 <= 0 ? 1.0L : (long double)(long long)min<__int128>(w128, (__int128)LLONG_MAX)); | |
| dens[i] = (wi <= 0 ? 0.0L : (long double)items[i].v / wi); | |
| } | |
| stable_sort(order.begin(), order.end(), [&](int a, int b){ | |
| if (dens[a] != dens[b]) return dens[a] > dens[b]; | |
| if (items[a].v != items[b].v) return items[a].v > items[b].v; | |
| __int128 wa = (__int128)items[a].m * wM1 + (__int128)items[a].l * wL1; | |
| __int128 wb = (__int128)items[b].m * wM1 + (__int128)items[b].l * wL1; | |
| return wa < wb; | |
| }); | |
| vector<BeamState> beam, nxt; | |
| beam.reserve(BEAM_W); | |
| nxt.reserve(BEAM_W * 20); | |
| BeamState init; | |
| init.remM = M; init.remL = L; init.val = 0; | |
| init.ub = (long double)init.val + fractional_bound(items, order, 0, init.remM, init.remL, M, L, wM1, wL1); | |
| beam.push_back(init); | |
| for (int pos = 0; pos < 12; pos++) { | |
| nxt.clear(); | |
| int it = order[pos]; | |
| for (const auto& st : beam) { | |
| long long remM = st.remM, remL = st.remL; | |
| long long maxTake = 0; | |
| if (items[it].m <= remM && items[it].l <= remL) { | |
| long long byM = remM / items[it].m; | |
| long long byL = remL / items[it].l; | |
| maxTake = min<long long>(items[it].q, min(byM, byL)); | |
| } | |
| // Generate more candidate values | |
| vector<int> cands; | |
| cands.reserve(30); | |
| cands.push_back(0); | |
| if (maxTake > 0) { | |
| cands.push_back((int)maxTake); | |
| // Small values | |
| for (int c = 1; c <= min<long long>(5, maxTake); c++) | |
| cands.push_back(c); | |
| // Percentage-based candidates | |
| for (int pct = 10; pct <= 90; pct += 10) | |
| cands.push_back((int)(maxTake * pct / 100)); | |
| // Near-max | |
| if (maxTake > 1) cands.push_back((int)(maxTake - 1)); | |
| if (maxTake > 2) cands.push_back((int)(maxTake - 2)); | |
| } | |
| sort(cands.begin(), cands.end()); | |
| cands.erase(unique(cands.begin(), cands.end()), cands.end()); | |
| for (int take : cands) { | |
| if (take < 0) continue; | |
| if ((long long)take > maxTake) continue; | |
| BeamState ns = st; | |
| ns.x[it] = take; | |
| ns.remM = remM - (long long)take * items[it].m; | |
| ns.remL = remL - (long long)take * items[it].l; | |
| ns.val = st.val + (long long)take * items[it].v; | |
| ns.ub = (long double)ns.val + fractional_bound(items, order, pos+1, ns.remM, ns.remL, M, L, wM1, wL1); | |
| nxt.push_back(ns); | |
| } | |
| } | |
| // Keep top BEAM_W by (ub, val) | |
| if ((int)nxt.size() > BEAM_W) { | |
| nth_element(nxt.begin(), nxt.begin() + BEAM_W, nxt.end(), [](const BeamState& a, const BeamState& b){ | |
| if (a.ub != b.ub) return a.ub > b.ub; | |
| return a.val > b.val; | |
| }); | |
| nxt.resize(BEAM_W); | |
| } | |
| sort(nxt.begin(), nxt.end(), [](const BeamState& a, const BeamState& b){ | |
| if (a.ub != b.ub) return a.ub > b.ub; | |
| return a.val > b.val; | |
| }); | |
| beam.swap(nxt); | |
| } | |
| Solution best; | |
| long long bestV = -1; | |
| for (const auto& st : beam) { | |
| if (st.val > bestV) { | |
| bestV = st.val; | |
| best.x = st.x; | |
| } | |
| } | |
| best.value = bestV; | |
| auto used = compute_used(items, best.x); | |
| best.usedM = used.first; | |
| best.usedL = used.second; | |
| return best; | |
| } | |
| // Deterministic pairwise swap improvement | |
| static Solution pairwise_improve(const vector<Item>& items, long long M, long long L, Solution sol) { | |
| auto used = compute_used(items, sol.x); | |
| long long remM = M - used.first; | |
| long long remL = L - used.second; | |
| bool improved = true; | |
| int iter = 0; | |
| while (improved && iter < 500) { | |
| improved = false; | |
| iter++; | |
| for (int i = 0; i < 12; i++) { | |
| if (sol.x[i] <= 0) continue; | |
| // Try removing t items of type i and adding as many of type j as possible | |
| int maxT = min(sol.x[i], 5); | |
| for (int t = 1; t <= maxT; t++) { | |
| long long freeM = (long long)t * items[i].m; | |
| long long freeL = (long long)t * items[i].l; | |
| long long lostVal = (long long)t * items[i].v; | |
| for (int j = 0; j < 12; j++) { | |
| if (i == j) continue; | |
| int avail_j = items[j].q - sol.x[j]; | |
| if (avail_j <= 0) continue; | |
| long long kM = (items[j].m > 0 ? (remM + freeM) / items[j].m : (long long)avail_j); | |
| long long kL = (items[j].l > 0 ? (remL + freeL) / items[j].l : (long long)avail_j); | |
| long long k = min<long long>(avail_j, min(kM, kL)); | |
| if (k <= 0) continue; | |
| long long gain = k * items[j].v - lostVal; | |
| if (gain > 0) { | |
| sol.x[i] -= t; | |
| sol.x[j] += (int)k; | |
| remM = remM + freeM - k * items[j].m; | |
| remL = remL + freeL - k * items[j].l; | |
| sol.value += gain; | |
| improved = true; | |
| goto next_iter; | |
| } | |
| } | |
| } | |
| } | |
| next_iter:; | |
| } | |
| // Also try adding items to remaining space | |
| for (int round = 0; round < 3; round++) { | |
| // Sort by value density | |
| vector<int> order(12); | |
| iota(order.begin(), order.end(), 0); | |
| sort(order.begin(), order.end(), [&](int a, int b) { | |
| long double da = (long double)items[a].v / ((long double)items[a].m / M + (long double)items[a].l / L); | |
| long double db = (long double)items[b].v / ((long double)items[b].m / M + (long double)items[b].l / L); | |
| return da > db; | |
| }); | |
| for (int id : order) { | |
| if (sol.x[id] >= items[id].q) continue; | |
| if (items[id].m > remM || items[id].l > remL) continue; | |
| long long add = min<long long>(items[id].q - sol.x[id], min(remM / items[id].m, remL / items[id].l)); | |
| if (add <= 0) continue; | |
| sol.x[id] += (int)add; | |
| remM -= add * items[id].m; | |
| remL -= add * items[id].l; | |
| sol.value += add * items[id].v; | |
| } | |
| } | |
| sol.usedM = M - remM; | |
| sol.usedL = L - remL; | |
| return sol; | |
| } | |
| static Solution local_improve( | |
| const vector<Item>& items, | |
| long long M, long long L, | |
| Solution sol, | |
| uint64_t seed, | |
| int ITER | |
| ) { | |
| vector<int> order(12); | |
| iota(order.begin(), order.end(), 0); | |
| vector<long double> dens(12, 0.0L); | |
| for (int i = 0; i < 12; i++) { | |
| __int128 w = (__int128)items[i].m * L + (__int128)items[i].l * M; | |
| long double wi = (w <= 0 ? 1.0L : (long double)(long long)min<__int128>(w, (__int128)LLONG_MAX)); | |
| dens[i] = (wi <= 0 ? 0.0L : (long double)items[i].v / wi); | |
| } | |
| stable_sort(order.begin(), order.end(), [&](int a, int b){ | |
| if (dens[a] != dens[b]) return dens[a] > dens[b]; | |
| return items[a].v > items[b].v; | |
| }); | |
| auto eval = [&](const array<int,12>& x, long long& usedM, long long& usedL, long long& val) { | |
| __int128 um = 0, ul = 0, vv = 0; | |
| for (int i = 0; i < 12; i++) { | |
| um += (__int128)x[i] * items[i].m; | |
| ul += (__int128)x[i] * items[i].l; | |
| vv += (__int128)x[i] * items[i].v; | |
| } | |
| usedM = (long long)um; | |
| usedL = (long long)ul; | |
| val = (long long)vv; | |
| }; | |
| auto refill_greedy = [&](array<int,12>& x) { | |
| long long usedM, usedL, val; | |
| eval(x, usedM, usedL, val); | |
| long long remM = M - usedM; | |
| long long remL = L - usedL; | |
| if (remM < 0 || remL < 0) return; | |
| for (int id : order) { | |
| int have = x[id]; | |
| int canMore = items[id].q - have; | |
| if (canMore <= 0) continue; | |
| if (items[id].m > remM || items[id].l > remL) continue; | |
| long long add = min<long long>(canMore, min(remM / items[id].m, remL / items[id].l)); | |
| if (add <= 0) continue; | |
| x[id] += (int)add; | |
| remM -= add * items[id].m; | |
| remL -= add * items[id].l; | |
| } | |
| }; | |
| mt19937_64 rng(seed); | |
| Solution best = sol; | |
| if (best.usedM > M || best.usedL > L) { | |
| best.x.fill(0); | |
| best = greedy(items, M, L, 1.0L/(long double)M, 1.0L/(long double)L); | |
| } | |
| vector<int> nonzero; | |
| nonzero.reserve(12); | |
| for (int it = 0; it < ITER; it++) { | |
| array<int,12> x = best.x; | |
| nonzero.clear(); | |
| for (int i = 0; i < 12; i++) if (x[i] > 0) nonzero.push_back(i); | |
| if (nonzero.empty()) break; | |
| int i = nonzero[(size_t)(rng() % nonzero.size())]; | |
| int maxRemove = min(x[i], 50); | |
| if (maxRemove <= 0) continue; | |
| int r = 1 + (int)(rng() % maxRemove); | |
| x[i] -= r; | |
| // occasional second removal to escape local maxima | |
| if ((rng() % 4) == 0) { | |
| nonzero.clear(); | |
| for (int j = 0; j < 12; j++) if (x[j] > 0) nonzero.push_back(j); | |
| if (!nonzero.empty()) { | |
| int j = nonzero[(size_t)(rng() % nonzero.size())]; | |
| int maxRemove2 = min(x[j], 30); | |
| if (maxRemove2 > 0) { | |
| int r2 = 1 + (int)(rng() % maxRemove2); | |
| x[j] -= r2; | |
| } | |
| } | |
| } | |
| // occasional third removal for deeper exploration | |
| if ((rng() % 8) == 0) { | |
| nonzero.clear(); | |
| for (int j = 0; j < 12; j++) if (x[j] > 0) nonzero.push_back(j); | |
| if (!nonzero.empty()) { | |
| int j = nonzero[(size_t)(rng() % nonzero.size())]; | |
| int maxRemove3 = min(x[j], 20); | |
| if (maxRemove3 > 0) { | |
| int r3 = 1 + (int)(rng() % maxRemove3); | |
| x[j] -= r3; | |
| } | |
| } | |
| } | |
| refill_greedy(x); | |
| long long usedM, usedL, val; | |
| eval(x, usedM, usedL, val); | |
| if (usedM <= M && usedL <= L && val > best.value) { | |
| best.x = x; | |
| best.value = val; | |
| best.usedM = usedM; | |
| best.usedL = usedL; | |
| } | |
| } | |
| return best; | |
| } | |
| static uint64_t hash_input(const string& s) { | |
| uint64_t h = 1469598103934665603ULL; | |
| for (unsigned char c : s) { | |
| h ^= (uint64_t)c; | |
| h *= 1099511628211ULL; | |
| } | |
| return h; | |
| } | |
| int main() { | |
| ios::sync_with_stdio(false); | |
| cin.tie(nullptr); | |
| auto start_time = chrono::steady_clock::now(); | |
| string input((istreambuf_iterator<char>(cin)), istreambuf_iterator<char>()); | |
| size_t i = 0; | |
| skip_ws(input, i); | |
| if (i >= input.size() || input[i] != '{') return 0; | |
| i++; | |
| vector<Item> items; | |
| items.reserve(12); | |
| vector<string> keyOrder; | |
| while (true) { | |
| skip_ws(input, i); | |
| if (i >= input.size()) break; | |
| if (input[i] == '}') { i++; break; } | |
| string key = parse_string(input, i); | |
| skip_ws(input, i); | |
| if (i < input.size() && input[i] == ':') i++; | |
| skip_ws(input, i); | |
| if (i < input.size() && input[i] == '[') i++; | |
| long long q = parse_int(input, i); | |
| skip_ws(input, i); if (i < input.size() && input[i] == ',') i++; | |
| long long v = parse_int(input, i); | |
| skip_ws(input, i); if (i < input.size() && input[i] == ',') i++; | |
| long long m = parse_int(input, i); | |
| skip_ws(input, i); if (i < input.size() && input[i] == ',') i++; | |
| long long l = parse_int(input, i); | |
| skip_ws(input, i); | |
| if (i < input.size() && input[i] == ']') i++; | |
| Item it; | |
| it.name = key; | |
| it.q = (int)q; | |
| it.v = v; | |
| it.m = m; | |
| it.l = l; | |
| items.push_back(it); | |
| keyOrder.push_back(key); | |
| skip_ws(input, i); | |
| if (i < input.size() && input[i] == ',') { i++; continue; } | |
| if (i < input.size() && input[i] == '}') { i++; break; } | |
| } | |
| int n = (int)items.size(); | |
| if (n == 0) { | |
| cout << "{}\n"; | |
| return 0; | |
| } | |
| if (n < 12) { | |
| while ((int)items.size() < 12) { | |
| Item dummy; | |
| dummy.name = "__dummy" + to_string(items.size()); | |
| dummy.q = 0; | |
| dummy.v = dummy.m = dummy.l = 0; | |
| items.push_back(dummy); | |
| keyOrder.push_back(dummy.name); | |
| } | |
| } | |
| if (n > 12) { | |
| items.resize(12); | |
| keyOrder.resize(12); | |
| n = 12; | |
| } | |
| const long long M = 20LL * 1000000LL; | |
| const long long L = 25LL * 1000000LL; | |
| vector<Solution> candidates; | |
| // Bulk greedy candidates | |
| { | |
| long double invM = 1.0L / (long double)M; | |
| long double invL = 1.0L / (long double)L; | |
| vector<pair<long double,long double>> wts = { | |
| {1.0L, 0.0L}, | |
| {0.0L, 1.0L}, | |
| {invM, invL}, | |
| {invM, 0.5L*invL}, | |
| {invM, 2.0L*invL}, | |
| {2.0L*invM, invL}, | |
| {0.5L*invM, invL}, | |
| {invM, 0.25L*invL}, | |
| {invM, 4.0L*invL}, | |
| {4.0L*invM, invL}, | |
| {0.25L*invM, invL} | |
| }; | |
| uint64_t h = hash_input(input); | |
| mt19937_64 rng(h ^ 0xA5A5A5A5A5A5A5A5ULL); | |
| for (int t = 0; t < 10; t++) { | |
| long double a = (long double)(rng() % 5000) / 1000.0L; | |
| long double b = (long double)(rng() % 5000) / 1000.0L; | |
| if (a < 0.05L && b < 0.05L) { a = invM; b = invL; } | |
| wts.push_back({a*invM, b*invL}); | |
| } | |
| for (auto [a,b] : wts) candidates.push_back(greedy(items, M, L, a, b)); | |
| } | |
| // One-at-a-time greedy candidates | |
| { | |
| vector<pair<int,double>> variants = { | |
| {0, 0.0}, {1, 0.0}, | |
| {2, 0.1}, {2, 0.2}, {2, 0.3}, {2, 0.4}, {2, 0.5}, {2, 0.6}, {2, 0.7}, {2, 0.8}, {2, 0.9}, | |
| {3, 0.1}, {3, 0.3}, {3, 0.5}, {3, 0.7}, {3, 0.9} | |
| }; | |
| for (auto [mode, gamma] : variants) { | |
| candidates.push_back(greedy_one_at_a_time(items, M, L, mode, gamma)); | |
| } | |
| } | |
| // Beam search candidates | |
| vector<WeightRun> runs; | |
| runs.push_back({1,1,true}); | |
| runs.push_back({0,1,true}); | |
| runs.push_back({1,0,true}); | |
| runs.push_back({1,4,true}); | |
| runs.push_back({1,2,true}); | |
| runs.push_back({2,1,true}); | |
| runs.push_back({4,1,true}); | |
| runs.push_back({8,1,true}); | |
| runs.push_back({1,8,true}); | |
| runs.push_back({1,4,false}); | |
| runs.push_back({1,2,false}); | |
| runs.push_back({2,1,false}); | |
| runs.push_back({4,1,false}); | |
| runs.push_back({3,2,true}); | |
| runs.push_back({2,3,true}); | |
| runs.push_back({3,1,true}); | |
| runs.push_back({1,3,true}); | |
| { | |
| uint64_t h = hash_input(input); | |
| mt19937_64 rng(h ^ 0x1234567890ABCDEFULL); | |
| for (int t = 0; t < 6; t++) { | |
| long long p = 1 + (long long)(rng() % 8); | |
| long long q = 1 + (long long)(rng() % 8); | |
| bool vol = (rng() & 1); | |
| runs.push_back({p,q,vol}); | |
| } | |
| } | |
| // Time-aware beam width | |
| auto elapsed_ms = [&]() { | |
| return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start_time).count(); | |
| }; | |
| int BEAM_W = 2000; | |
| for (auto &wr : runs) { | |
| if (elapsed_ms() > 600) { BEAM_W = 500; } | |
| if (elapsed_ms() > 800) break; | |
| candidates.push_back(beam_search(items, M, L, wr, BEAM_W)); | |
| } | |
| // Choose best candidate | |
| Solution best; | |
| best.value = -1; | |
| for (auto &s : candidates) { | |
| auto used = compute_used(items, s.x); | |
| s.usedM = used.first; | |
| s.usedL = used.second; | |
| if (s.usedM <= M && s.usedL <= L && s.value > best.value) best = s; | |
| } | |
| // Pairwise deterministic improvement | |
| best = pairwise_improve(items, M, L, best); | |
| // Also try pairwise on top candidates | |
| { | |
| vector<Solution> top_candidates; | |
| sort(candidates.begin(), candidates.end(), [](const Solution& a, const Solution& b) { | |
| return a.value > b.value; | |
| }); | |
| int limit = min((int)candidates.size(), 5); | |
| for (int ci = 0; ci < limit && elapsed_ms() < 750; ci++) { | |
| Solution improved = pairwise_improve(items, M, L, candidates[ci]); | |
| if (improved.usedM <= M && improved.usedL <= L && improved.value > best.value) { | |
| best = improved; | |
| } | |
| } | |
| } | |
| // Local improvement with remaining time | |
| { | |
| long long remaining_ms = 900 - elapsed_ms(); | |
| int iter_count = max(1000, (int)(remaining_ms * 80)); // ~80 iterations per ms | |
| uint64_t seed = hash_input(input) ^ 0x9E3779B97F4A7C15ULL; | |
| best = local_improve(items, M, L, best, seed, iter_count); | |
| // Second round with different seed | |
| if (elapsed_ms() < 850) { | |
| remaining_ms = 900 - elapsed_ms(); | |
| iter_count = max(1000, (int)(remaining_ms * 80)); | |
| best = local_improve(items, M, L, best, seed ^ 0xDEADBEEFCAFEBABEULL, iter_count); | |
| } | |
| } | |
| // Final pairwise | |
| if (elapsed_ms() < 950) { | |
| best = pairwise_improve(items, M, L, best); | |
| } | |
| // Output JSON in original key order | |
| cout << "{\n"; | |
| for (int k = 0; k < n; k++) { | |
| cout << " \"" << items[k].name << "\": " << best.x[k]; | |
| if (k + 1 < n) cout << ",\n"; | |
| else cout << "\n"; | |
| } | |
| cout << "}\n"; | |
| return 0; | |
| } | |