Submission #1251064

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

souvenirs

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

struct Equation {
    vector<int> elem; long long sum;
    
    Equation(vector<int> e, long long s) : elem(e), sum(s) {}
    
    void clear(vector<long long>& P, int bottom) {
        while (elem.back() > bottom) { // elem[0] should not be less than bottom, so no need to check elem.empty();
            sum -= P[elem.back()];
            elem.pop_back();
        }
    }
};

Equation modified_transaction(long long M) {
    pair<vector<int>, long long> raw = transaction(M);
    return {raw.first, M - raw.second};
}

void buy_souvenirs(int N, long long P0) {
    vector<long long> P(N, 0);
    vector<int> kpi(N); // track how many of each type has been bought
    for (int i = 0; i < N; i++) kpi[i] = i;
    stack<Equation> S; // store info
    int bottom = N - 1; // found P[i] forall i > bottom;
    S.push({{0}, P0});
    // find P
    while (bottom) {
        Equation u = S.top();
        u.clear(P, bottom);
        if (u.elem.size() == 1 && u.elem[0] == bottom) {
            S.pop();
            P[bottom] = u.sum;
            bottom--;
        } else {
            long long amount = (u.sum - 1)/u.elem.size();
            Equation next = modified_transaction(amount);
            for (auto i: next.elem) kpi[i]--;
            S.push(next);
        }
    }
    // clean up
    for (int i = 0; i < N; i++) while (kpi[i]--) transaction(P[i]);
}

• 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