docker_space/frontier_cs_1/solution.cpp

#include <bits/stdc++.h>
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;
}