Submission #1254596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254596		TrendBattles	Souvenirs (IOI25_souvenirs)	C++17	25 / 100	12 ms	412 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using lli = long long;

const lli inf_64 = 0x3f3f3f3f3f3f3f3f;

void buy_souvenirs(int N, lli P0) {
    vector <lli> cost(N, -1);
    vector <int> times(N);
    cost[0] = P0;

    auto Trim = [&] (vector <int>& item_idx, lli& total) -> void {
        vector <int> new_list;
        for (int p : item_idx) {
            if (cost[p] != -1) {
                total -= cost[p];
            } else {
                new_list.push_back(p);
            }
        }

        item_idx = move(new_list);
    };

    auto Min_Sum = [&] (lli r, vector <int> item_idx) -> lli {
        lli sum = r;
        int p = (int) item_idx.size() - 2;

        for (int i = item_idx.back() - 1; i >= item_idx[0]; --i) {
            r += 1;
            if (cost[i] != -1) r = max(r, cost[i]);

            if (item_idx[p] == i) {
                sum += r; --p;
            }
        }

        return sum;
    };

    auto Solve = [&] (auto self, vector <int> item_idx, lli total) -> void {
        // cerr << "DEBUG" << '\n';
        // for (int p : item_idx) cerr << p << " ";
        // cerr << "\n" << total << "\n";

        for (int p : item_idx) {
            times[p] += 1;
        }

        Trim(item_idx, total);

        while ((int) item_idx.size() > 1) {
            lli v_l = 0, v_r = inf_64;

            for (int i = 0; i < item_idx.back(); ++i) {
                v_r -= 1;
                if (cost[i] != -1) v_r = min(v_r, cost[i]);
            }
            v_r -= 1;

            for (int i = N - 1; i > item_idx.back(); --i) {
                v_l += 1;
                if (cost[i] != -1) v_l = max(v_l, cost[i]);
            }
            v_l += 1;

            while (v_l <= v_r) {
                lli v_mid = (v_l + v_r) >> 1;

                if (Min_Sum(v_mid, item_idx) <= total) {
                    v_l = v_mid + 1;
                } else {
                    v_r = v_mid - 1;
                }
            }

            vector <int> new_idx;
            lli new_total;

            tie(new_idx, new_total) = transaction(v_r);
            new_total = v_r - new_total;

            self(self, new_idx, new_total);

            Trim(item_idx, total);
        }

        if (not item_idx.empty()) {
            cost[item_idx[0]] = total;
        }
    };
    for (int i = 1; i < N; ++i) {
        if (cost[i] != -1) return;

        // cerr << "ASK FOR: " << i << " " << cost[i - 1] - 1 << '\n';

        vector <int> item_idx;
        lli value;
        
        tie(item_idx, value) = transaction(cost[i - 1] - 1);
        value = cost[i - 1] - 1 - value;

        Solve(Solve, item_idx, value);
    }

    for (int i = 0; i < N; ++i) {
        assert(cost[i] != -1);
        
        while (times[i] < i) {
            ++times[i];
            transaction(cost[i]);
        }
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 4 / 4
• Subtask 2: 3 / 3
• Subtask 3: 0 / 14
• Subtask 4: 18 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33