Download docker_space/frontier_cs_1/examples/gemini3pro_4.cpp from JustinTX/shinka-backup: direct link, hf CLI and curl.
- Browser
- Download file 8.76 kB
-
https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_1/examples/gemini3pro_4.cpp
- Command line
-
hf download hf://JustinTX/shinka-backup/docker_space/frontier_cs_1/examples/gemini3pro_4.cpp
-
curl -L -o gemini3pro_4.cpp https://huggingface.co/JustinTX/shinka-backup/resolve/main/docker_space/frontier_cs_1/examples/gemini3pro_4.cpp
8.76 kB
| using namespace std; | |
| // Problem constants | |
| const long long MAX_M = 20000000; | |
| const long long MAX_L = 25000000; | |
| struct Item { | |
| string name; | |
| int q; | |
| long long v, m, l; | |
| int original_index; | |
| }; | |
| struct Solution { | |
| vector<int> counts; | |
| long long total_v; | |
| long long total_m; | |
| long long total_l; | |
| }; | |
| vector<Item> items; | |
| vector<string> key_order; | |
| Solution best_sol; | |
| // Parse JSON from stdin | |
| void parse_input() { | |
| string data; | |
| char c; | |
| while (cin.get(c)) data += c; | |
| size_t n = data.size(); | |
| size_t i = 0; | |
| while (i < n) { | |
| // Find start of a key string | |
| while (i < n && data[i] != '"') i++; | |
| if (i >= n) break; | |
| i++; // skip " | |
| string key = ""; | |
| while (i < n && data[i] != '"') { | |
| key += data[i]; | |
| i++; | |
| } | |
| i++; // skip closing " | |
| // Search for colon to confirm it's a key | |
| size_t temp_i = i; | |
| while (temp_i < n && isspace(data[temp_i])) temp_i++; | |
| if (temp_i >= n || data[temp_i] != ':') { | |
| // Not a key-value pair we are interested in (or end of file) | |
| i = temp_i; | |
| continue; | |
| } | |
| i = temp_i + 1; // skip : | |
| // Search for array start | |
| while (i < n && data[i] != '[') i++; | |
| if (i >= n) break; | |
| i++; // skip [ | |
| // Parse 4 numbers | |
| long long vals[4]; | |
| for (int k = 0; k < 4; ++k) { | |
| while (i < n && !isdigit(data[i])) i++; | |
| string num_s = ""; | |
| while (i < n && isdigit(data[i])) { | |
| num_s += data[i]; | |
| i++; | |
| } | |
| if (!num_s.empty()) vals[k] = stoll(num_s); | |
| else vals[k] = 0; | |
| } | |
| Item item; | |
| item.name = key; | |
| item.q = (int)vals[0]; | |
| item.v = vals[1]; | |
| item.m = vals[2]; | |
| item.l = vals[3]; | |
| item.original_index = items.size(); | |
| items.push_back(item); | |
| key_order.push_back(key); | |
| // skip until ] | |
| while (i < n && data[i] != ']') i++; | |
| i++; | |
| } | |
| } | |
| int main() { | |
| ios_base::sync_with_stdio(false); | |
| cin.tie(NULL); | |
| parse_input(); | |
| int N = items.size(); | |
| if (N == 0) { | |
| cout << "{}" << endl; | |
| return 0; | |
| } | |
| // Map name to index for easy lookup later | |
| map<string, int> name_to_idx; | |
| for (int i = 0; i < N; ++i) { | |
| name_to_idx[items[i].name] = i; | |
| } | |
| // Initialize best solution | |
| best_sol.counts.assign(N, 0); | |
| best_sol.total_v = 0; | |
| best_sol.total_m = 0; | |
| best_sol.total_l = 0; | |
| mt19937 rng(12345); | |
| clock_t start_time = clock(); | |
| // Phase 1: GRASP (Greedy Randomized Adaptive Search Procedure) | |
| // Run for 40% of allowed time | |
| while ((double)(clock() - start_time) / CLOCKS_PER_SEC < 0.4) { | |
| // Random alpha for linear combination of constraints | |
| double alpha = (double)(rng() % 1001) / 1000.0; | |
| vector<int> p(N); | |
| for (int k = 0; k < N; ++k) p[k] = k; | |
| // Randomized sorting based on value density | |
| shuffle(p.begin(), p.end(), rng); | |
| sort(p.begin(), p.end(), [&](int a, int b) { | |
| double m_norm_a = (double)items[a].m / MAX_M; | |
| double l_norm_a = (double)items[a].l / MAX_L; | |
| double cost_a = alpha * m_norm_a + (1.0 - alpha) * l_norm_a; | |
| double m_norm_b = (double)items[b].m / MAX_M; | |
| double l_norm_b = (double)items[b].l / MAX_L; | |
| double cost_b = alpha * m_norm_b + (1.0 - alpha) * l_norm_b; | |
| if (cost_a <= 1e-12) return true; | |
| if (cost_b <= 1e-12) return false; | |
| double score_a = items[a].v / cost_a; | |
| double score_b = items[b].v / cost_b; | |
| return score_a > score_b; | |
| }); | |
| Solution curr; | |
| curr.counts.assign(N, 0); | |
| curr.total_v = 0; | |
| curr.total_m = 0; | |
| curr.total_l = 0; | |
| for (int idx : p) { | |
| long long rem_m = MAX_M - curr.total_m; | |
| long long rem_l = MAX_L - curr.total_l; | |
| int can_take = items[idx].q; | |
| if (items[idx].m > 0) can_take = min((long long)can_take, rem_m / items[idx].m); | |
| if (items[idx].l > 0) can_take = min((long long)can_take, rem_l / items[idx].l); | |
| if (can_take > 0) { | |
| curr.counts[idx] = can_take; | |
| curr.total_v += (long long)can_take * items[idx].v; | |
| curr.total_m += (long long)can_take * items[idx].m; | |
| curr.total_l += (long long)can_take * items[idx].l; | |
| } | |
| } | |
| if (curr.total_v > best_sol.total_v) { | |
| best_sol = curr; | |
| } | |
| } | |
| // Phase 2: Local Search / Hill Climbing | |
| // Start from best found in GRASP | |
| Solution curr = best_sol; | |
| vector<int> candidates; | |
| candidates.reserve(N); | |
| int iter = 0; | |
| while (true) { | |
| iter++; | |
| // Check time every 1024 iterations | |
| if ((iter & 1023) == 0) { | |
| if ((double)(clock() - start_time) / CLOCKS_PER_SEC > 0.98) break; | |
| } | |
| Solution next_sol = curr; | |
| int move_type = rng() % 3; | |
| if (move_type == 0) { | |
| // Move: Add item and Repair if needed | |
| int idx = rng() % N; | |
| if (next_sol.counts[idx] < items[idx].q) { | |
| next_sol.counts[idx]++; | |
| next_sol.total_v += items[idx].v; | |
| next_sol.total_m += items[idx].m; | |
| next_sol.total_l += items[idx].l; | |
| // Repair if invalid | |
| while (next_sol.total_m > MAX_M || next_sol.total_l > MAX_L) { | |
| candidates.clear(); | |
| for(int k=0; k<N; ++k) if(next_sol.counts[k] > 0) candidates.push_back(k); | |
| if(candidates.empty()) break; | |
| int victim = candidates[rng() % candidates.size()]; | |
| next_sol.counts[victim]--; | |
| next_sol.total_v -= items[victim].v; | |
| next_sol.total_m -= items[victim].m; | |
| next_sol.total_l -= items[victim].l; | |
| } | |
| // If valid and not worse, accept | |
| if (next_sol.total_m <= MAX_M && next_sol.total_l <= MAX_L) { | |
| if (next_sol.total_v >= curr.total_v) { | |
| curr = next_sol; | |
| if (curr.total_v > best_sol.total_v) best_sol = curr; | |
| } | |
| } | |
| } | |
| } else if (move_type == 1) { | |
| // Move: Swap (Add i, Remove j) | |
| int i = rng() % N; | |
| int j = rng() % N; | |
| if (i != j && next_sol.counts[i] < items[i].q && next_sol.counts[j] > 0) { | |
| next_sol.counts[i]++; | |
| next_sol.total_v += items[i].v; | |
| next_sol.total_m += items[i].m; | |
| next_sol.total_l += items[i].l; | |
| next_sol.counts[j]--; | |
| next_sol.total_v -= items[j].v; | |
| next_sol.total_m -= items[j].m; | |
| next_sol.total_l -= items[j].l; | |
| // Only accept if valid and not worse | |
| if (next_sol.total_m <= MAX_M && next_sol.total_l <= MAX_L) { | |
| if (next_sol.total_v >= curr.total_v) { | |
| curr = next_sol; | |
| if (curr.total_v > best_sol.total_v) best_sol = curr; | |
| } | |
| } | |
| } | |
| } else { | |
| // Move: Fill slack (Add only, valid check immediately) | |
| int idx = rng() % N; | |
| if (next_sol.counts[idx] < items[idx].q) { | |
| if (next_sol.total_m + items[idx].m <= MAX_M && | |
| next_sol.total_l + items[idx].l <= MAX_L) { | |
| next_sol.counts[idx]++; | |
| next_sol.total_v += items[idx].v; | |
| next_sol.total_m += items[idx].m; | |
| next_sol.total_l += items[idx].l; | |
| curr = next_sol; | |
| if (curr.total_v > best_sol.total_v) best_sol = curr; | |
| } | |
| } | |
| } | |
| } | |
| // Output JSON | |
| cout << "{" << endl; | |
| for (size_t i = 0; i < key_order.size(); ++i) { | |
| string key = key_order[i]; | |
| int idx = name_to_idx[key]; | |
| cout << " \"" << key << "\": " << best_sol.counts[idx]; | |
| if (i < key_order.size() - 1) cout << ","; | |
| cout << endl; | |
| } | |
| cout << "}" << endl; | |
| return 0; | |
| } |