Submission #1253349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253349		fve5	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	420 KiB

souvenirs

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

typedef long long i64;

int N;
vector<optional<i64>> costs;
vector<int> buy_count;

struct Purchase {
    i64 cost;
    vector<int> items;
};

void solve_suffix(int start);
void shorten(Purchase purchase);

Purchase process(Purchase purchase) {
    auto [cost, items] = purchase;

    for (int i = 0; i < items.size(); i++) {
        if (costs[items[i]]) {
            cost -= costs[items[i]].value();
            swap(items[i], items.back());
            items.pop_back();
            i--;
        }
    }

    return {cost, items};
}

Purchase query(i64 paid) {
    auto [items, cost] = transaction(paid);
    for (auto x: items) buy_count[x]++;
    return {paid - cost, items};
}

void shorten(Purchase purchase) {
    while (purchase.items.size() != 1) {
        i64 ask = purchase.cost / purchase.items.size();
        shorten(process(query(ask)));
        purchase = process(purchase);
    }
    costs[purchase.items[0]] = purchase.cost;
    solve_suffix(purchase.items[0] + 1);
    i64 ask = purchase.cost / purchase.items.size();
}

void solve_suffix(int start) {
    if (start == N || costs[start]) return;
    i64 bound = costs[start - 1].value();
    shorten(process(query(bound - 1)));
}

void buy_souvenirs(int N, long long P0) {
    ::N = N;
    costs.resize(N);
    buy_count.resize(N);
    costs[0] = P0;
    solve_suffix(1);

    for (int i = 0; i < N; i++)
        while (buy_count[i] < i)
            query(costs[i].value());
}

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