File size: 5,798 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 | #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <functional>
#include <numeric>
#include "nlohmann/json.hpp"
using json = nlohmann::json;
const long long MAX_MASS = 20000000;
const long long MAX_VOLUME = 25000000;
struct Item {
std::string name;
int q;
long long v, m, l;
};
struct Solution {
std::vector<int> counts;
long long value = 0;
long long mass = 0;
long long volume = 0;
Solution(int num_items) : counts(num_items, 0) {}
};
void calculate_stats(const std::vector<Item>& items, Solution& sol) {
sol.value = 0;
sol.mass = 0;
sol.volume = 0;
for (size_t i = 0; i < items.size(); ++i) {
sol.value += (long long)sol.counts[i] * items[i].v;
sol.mass += (long long)sol.counts[i] * items[i].m;
sol.volume += (long long)sol.counts[i] * items[i].l;
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
json input_json;
std::cin >> input_json;
std::vector<Item> items;
for (auto& [key, val] : input_json.items()) {
items.push_back({
key,
val[0].get<int>(),
val[1].get<long long>(),
val[2].get<long long>(),
val[3].get<long long>()
});
}
int num_items = items.size();
// --- Greedy Phase ---
std::vector<Solution> initial_solutions;
std::vector<std::function<double(const Item&)>> metrics;
metrics.push_back([](const Item& i){ return i.m > 0 ? (double)i.v / i.m : (i.v > 0 ? 1e18 : 0); });
metrics.push_back([](const Item& i){ return i.l > 0 ? (double)i.v / i.l : (i.v > 0 ? 1e18 : 0); });
metrics.push_back([](const Item& i){ return (i.m + i.l) > 0 ? (double)i.v / (double)(i.m + i.l) : (i.v > 0 ? 1e18 : 0); });
metrics.push_back([](const Item& i){ return (double)i.v; });
metrics.push_back([](const Item& i){
double norm_res = (double)i.m / MAX_MASS + (double)i.l / MAX_VOLUME;
return norm_res > 1e-9 ? (double)i.v / norm_res : (i.v > 0 ? 1e18 : 0);
});
struct IndividualItem {
double metric_val;
int type_idx;
};
for (const auto& metric : metrics) {
Solution sol(num_items);
std::vector<IndividualItem> all_items_list;
for (int i = 0; i < num_items; ++i) {
if (items[i].m <= 0 && items[i].l <= 0) continue;
double mval = metric(items[i]);
for (int j = 0; j < items[i].q; ++j) {
all_items_list.push_back({mval, i});
}
}
std::sort(all_items_list.begin(), all_items_list.end(), [](const IndividualItem& a, const IndividualItem& b){
return a.metric_val > b.metric_val;
});
// This greedy approach packs items one by one.
// It's more granular than packing in chunks.
for (const auto& indiv_item : all_items_list) {
int idx = indiv_item.type_idx;
if (sol.mass + items[idx].m <= MAX_MASS && sol.volume + items[idx].l <= MAX_VOLUME) {
sol.counts[idx]++;
sol.mass += items[idx].m;
sol.volume += items[idx].l;
sol.value += items[idx].v;
}
}
initial_solutions.push_back(sol);
}
Solution best_sol(num_items);
if (!initial_solutions.empty()) {
best_sol = *std::max_element(initial_solutions.begin(), initial_solutions.end(),
[](const Solution& a, const Solution& b){
return a.value < b.value;
});
}
// --- Local Search Phase (Steepest Ascent Hill Climbing) ---
bool improved = true;
while(improved) {
improved = false;
long long best_val_change = 0;
int move_type = -1; // 0: add, 1: swap
int add_idx = -1, rem_idx = -1;
// Try adding one item
for (int i = 0; i < num_items; ++i) {
if (best_sol.counts[i] < items[i].q &&
best_sol.mass + items[i].m <= MAX_MASS &&
best_sol.volume + items[i].l <= MAX_VOLUME) {
if (items[i].v > best_val_change) {
best_val_change = items[i].v;
move_type = 0;
add_idx = i;
}
}
}
// Try swapping one item for another
for (int i = 0; i < num_items; ++i) { // item to remove
if (best_sol.counts[i] == 0) continue;
for (int j = 0; j < num_items; ++j) { // item to add
if (i == j || best_sol.counts[j] >= items[j].q) continue;
long long next_mass = best_sol.mass - items[i].m + items[j].m;
long long next_vol = best_sol.volume - items[i].l + items[j].l;
if (next_mass <= MAX_MASS && next_vol <= MAX_VOLUME) {
long long val_change = items[j].v - items[i].v;
if (val_change > best_val_change) {
best_val_change = val_change;
move_type = 1;
rem_idx = i;
add_idx = j;
}
}
}
}
if (best_val_change > 0) {
improved = true;
if (move_type == 0) { // Add
best_sol.counts[add_idx]++;
} else if (move_type == 1) { // Swap
best_sol.counts[rem_idx]--;
best_sol.counts[add_idx]++;
}
calculate_stats(items, best_sol);
}
}
// --- Output ---
json output_json;
for (int i = 0; i < num_items; ++i) {
output_json[items[i].name] = best_sol.counts[i];
}
std::cout << output_json.dump(2) << std::endl;
return 0;
} |