Download docker_space/frontier_cs_1/examples/gemini3pro_1.cpp from JustinTX/shinka-backup: direct link, hf CLI and curl.
- Browser
- Download file 10.3 kB
-
https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_1/examples/gemini3pro_1.cpp
- Command line
-
hf download hf://JustinTX/shinka-backup/docker_space/frontier_cs_1/examples/gemini3pro_1.cpp
-
curl -L -o gemini3pro_1.cpp https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_1/examples/gemini3pro_1.cpp
10.3 kB
| using namespace std; | |
| // Problem Constants | |
| const long long MAX_MASS_MG = 20000000; | |
| const long long MAX_VOL_UL = 25000000; | |
| struct Item { | |
| string name; | |
| int id; | |
| long long q; | |
| long long v; | |
| long long m; | |
| long long l; | |
| }; | |
| // Solution state | |
| struct Solution { | |
| vector<long long> counts; | |
| long long current_m; | |
| long long current_l; | |
| long long current_v; | |
| Solution(int n) : counts(n, 0), current_m(0), current_l(0), current_v(0) {} | |
| }; | |
| int main() { | |
| // Optimize I/O operations | |
| ios_base::sync_with_stdio(false); | |
| cin.tie(NULL); | |
| // Parse Input | |
| // Reading all stdin into a string | |
| string raw_input; | |
| string line; | |
| while(getline(cin, line)) { | |
| raw_input += line + " "; | |
| } | |
| // Replace JSON delimiters with spaces to simplify parsing | |
| for(char &c : raw_input) { | |
| if (c == '{' || c == '}' || c == '[' || c == ']' || c == ',' || c == '"' || c == ':') { | |
| c = ' '; | |
| } | |
| } | |
| stringstream ss(raw_input); | |
| string key; | |
| vector<Item> items; | |
| int id_gen = 0; | |
| // Parse loop | |
| while(ss >> key) { | |
| Item item; | |
| item.name = key; | |
| item.id = id_gen++; | |
| if (!(ss >> item.q >> item.v >> item.m >> item.l)) break; | |
| items.push_back(item); | |
| } | |
| int N = items.size(); | |
| if (N == 0) { | |
| cout << "{}" << endl; | |
| return 0; | |
| } | |
| // Random engine | |
| mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); | |
| // Track best solution | |
| long long best_v = -1; | |
| vector<long long> best_counts(N, 0); | |
| // Time control | |
| clock_t start_clock = clock(); | |
| double time_limit = 0.95; // Use slightly less than 1.0s to be safe | |
| // Auxiliary vector for item indices | |
| vector<int> indices(N); | |
| for(int i=0; i<N; ++i) indices[i] = i; | |
| // Main Optimization Loop | |
| while (true) { | |
| // Check time limit | |
| if ((double)(clock() - start_clock) / CLOCKS_PER_SEC > time_limit) break; | |
| // 1. Randomized Greedy Construction | |
| // Generate random weights for scoring metric | |
| uniform_real_distribution<double> dist01(0.0, 1.0); | |
| double w_mass = dist01(rng); | |
| // Occasionally try pure strategies | |
| double rand_strat = dist01(rng); | |
| if (rand_strat < 0.1) w_mass = 1.0; | |
| else if (rand_strat < 0.2) w_mass = 0.0; | |
| double w_vol = 1.0 - w_mass; | |
| // Rank items | |
| vector<pair<double, int>> ranked(N); | |
| for(int i=0; i<N; ++i) { | |
| double cost = 0; | |
| // Normalized cost | |
| if (MAX_MASS_MG > 0) cost += w_mass * ((double)items[i].m / MAX_MASS_MG); | |
| if (MAX_VOL_UL > 0) cost += w_vol * ((double)items[i].l / MAX_VOL_UL); | |
| if (cost < 1e-15) cost = 1e-15; | |
| double score = (double)items[i].v / cost; | |
| // Add multiplicative noise to score to explore local variations | |
| double noise = dist01(rng) * 0.4 + 0.8; // Range [0.8, 1.2] | |
| ranked[i] = {score * noise, i}; | |
| } | |
| sort(ranked.rbegin(), ranked.rend()); | |
| // Fill greedily | |
| Solution sol(N); | |
| for(auto& p : ranked) { | |
| int idx = p.second; | |
| long long rem_m = MAX_MASS_MG - sol.current_m; | |
| long long rem_l = MAX_VOL_UL - sol.current_l; | |
| long long count = items[idx].q; | |
| if (items[idx].m > 0) count = min(count, rem_m / items[idx].m); | |
| if (items[idx].l > 0) count = min(count, rem_l / items[idx].l); | |
| sol.counts[idx] = count; | |
| sol.current_m += count * items[idx].m; | |
| sol.current_l += count * items[idx].l; | |
| sol.current_v += count * items[idx].v; | |
| } | |
| // 2. Local Search | |
| // Phase A: Fill Gaps | |
| // Try to add any item that fits | |
| shuffle(indices.begin(), indices.end(), rng); | |
| bool changed = true; | |
| while(changed) { | |
| changed = false; | |
| for(int idx : indices) { | |
| if (sol.counts[idx] < items[idx].q) { | |
| long long rem_m = MAX_MASS_MG - sol.current_m; | |
| long long rem_l = MAX_VOL_UL - sol.current_l; | |
| long long can_add = items[idx].q - sol.counts[idx]; | |
| if (items[idx].m > 0) can_add = min(can_add, rem_m / items[idx].m); | |
| if (items[idx].l > 0) can_add = min(can_add, rem_l / items[idx].l); | |
| if (can_add > 0) { | |
| sol.counts[idx] += can_add; | |
| sol.current_m += can_add * items[idx].m; | |
| sol.current_l += can_add * items[idx].l; | |
| sol.current_v += can_add * items[idx].v; | |
| changed = true; | |
| } | |
| } | |
| } | |
| } | |
| // Phase B: Pairwise Exchange | |
| // Try to force add item j by removing items of type i | |
| bool improved = true; | |
| while(improved) { | |
| improved = false; | |
| // Check time inside local search to prevent timeout in edge cases | |
| if ((double)(clock() - start_clock) / CLOCKS_PER_SEC > time_limit) break; | |
| for(int i : indices) { // Candidate to remove | |
| if (sol.counts[i] == 0) continue; | |
| for(int j : indices) { // Candidate to add | |
| if (i == j || sol.counts[j] >= items[j].q) continue; | |
| // We want to add at least 1 item of j. | |
| long long rem_m = MAX_MASS_MG - sol.current_m; | |
| long long rem_l = MAX_VOL_UL - sol.current_l; | |
| long long need_m = (items[j].m > rem_m) ? (items[j].m - rem_m) : 0; | |
| long long need_l = (items[j].l > rem_l) ? (items[j].l - rem_l) : 0; | |
| if (need_m == 0 && need_l == 0) { | |
| // Fits without removal (should be handled by gap fill, but safe to have) | |
| long long take = 1; | |
| sol.counts[j] += take; | |
| sol.current_m += items[j].m; | |
| sol.current_l += items[j].l; | |
| sol.current_v += items[j].v; | |
| improved = true; | |
| goto next_iter; | |
| } | |
| // Calculate minimum items of i to remove to fit 1 j | |
| long long remove_i = 0; | |
| bool possible = true; | |
| if (need_m > 0) { | |
| if (items[i].m == 0) { possible = false; } | |
| else remove_i = max(remove_i, (need_m + items[i].m - 1) / items[i].m); | |
| } | |
| if (possible && need_l > 0) { | |
| if (items[i].l == 0) { possible = false; } | |
| else remove_i = max(remove_i, (need_l + items[i].l - 1) / items[i].l); | |
| } | |
| if (!possible || remove_i > sol.counts[i]) continue; | |
| // Tentative Swap | |
| // Remove k items of i | |
| long long old_count_i = sol.counts[i]; | |
| long long old_count_j = sol.counts[j]; | |
| long long old_m = sol.current_m; | |
| long long old_l = sol.current_l; | |
| long long old_v = sol.current_v; | |
| sol.counts[i] -= remove_i; | |
| sol.current_m -= remove_i * items[i].m; | |
| sol.current_l -= remove_i * items[i].l; | |
| sol.current_v -= remove_i * items[i].v; | |
| // Fill with j as much as possible | |
| long long can_add_j = items[j].q - sol.counts[j]; | |
| long long room_m = MAX_MASS_MG - sol.current_m; | |
| long long room_l = MAX_VOL_UL - sol.current_l; | |
| if (items[j].m > 0) can_add_j = min(can_add_j, room_m / items[j].m); | |
| if (items[j].l > 0) can_add_j = min(can_add_j, room_l / items[j].l); | |
| if (can_add_j < 1) { | |
| // Should not happen if logic is correct, but sanity check | |
| // Revert | |
| sol.counts[i] = old_count_i; | |
| sol.counts[j] = old_count_j; | |
| sol.current_m = old_m; | |
| sol.current_l = old_l; | |
| sol.current_v = old_v; | |
| continue; | |
| } | |
| sol.counts[j] += can_add_j; | |
| sol.current_m += can_add_j * items[j].m; | |
| sol.current_l += can_add_j * items[j].l; | |
| sol.current_v += can_add_j * items[j].v; | |
| // Check improvement | |
| if (sol.current_v > old_v) { | |
| improved = true; | |
| goto next_iter; | |
| } else { | |
| // Revert | |
| sol.counts[i] = old_count_i; | |
| sol.counts[j] = old_count_j; | |
| sol.current_m = old_m; | |
| sol.current_l = old_l; | |
| sol.current_v = old_v; | |
| } | |
| } | |
| } | |
| next_iter:; | |
| } | |
| // Update Global Best | |
| if (sol.current_v > best_v) { | |
| best_v = sol.current_v; | |
| best_counts = sol.counts; | |
| } | |
| } | |
| // Output Result | |
| cout << "{" << endl; | |
| for(int i=0; i<N; ++i) { | |
| cout << " \"" << items[i].name << "\": " << best_counts[i]; | |
| if (i < N - 1) cout << ","; | |
| cout << endl; | |
| } | |
| cout << "}" << endl; | |
| return 0; | |
| } |