Submission #1252572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252572		anfi	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	412 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int MAXN = 105;

int n, last_idx;
ll p[MAXN];
int cnt_visit[MAXN];

ll calc_next(ll s, int k) {
    s += (ll)k * (k - 1) / 2 + k - 1;
    return s / k;
}

struct Frame {
    ll money;
    vector<int> v;
    ll sum;
    int stage; 
};

void build_iterative(ll initial_money) {
    vector<Frame> stk;
    stk.reserve(MAXN);
    stk.push_back({initial_money, {}, 0, 0});

    while (!stk.empty()) {
        Frame &f = stk.back();
        if (f.stage == 0) {
            auto [v, remain] = transaction(f.money);
            ll s = f.money - remain;
            f.v = v;
            f.sum = s;
            for (int idx : f.v) cnt_visit[idx]++;
            f.stage = 1;
        }
        else if (f.stage == 1 || f.stage == 2) {
            if (!f.v.empty() && f.v[0] < last_idx) {
                while (!f.v.empty() && f.v.back() >= last_idx) {
                    f.sum -= p[f.v.back()];
                    f.v.pop_back();
                }
                if (!f.v.empty() && f.v[0] + 1 != last_idx) {
                    f.stage = 2;
                    ll next_money = calc_next(f.sum, f.v.size()) - 1;
                    stk.push_back({next_money, {}, 0, 0});
                    continue;
                }
            }
            f.stage = 3;
        }
        else if (f.stage == 3) {
            if (!f.v.empty()) {
                int idx = f.v[0];
                p[idx] = f.sum;
                last_idx = idx;
            }
            stk.pop_back();
        }
    }
}

void buy_souvenirs(int N, ll P0) {
    n = N;
    last_idx = N;
    memset(p, 0, sizeof(p));
    memset(cnt_visit, 0, sizeof(cnt_visit));
    p[0] = P0;

    build_iterative(P0 - 1);

    for (int i = 1; i < n; ++i) {
        while (cnt_visit[i] < i) {
            transaction(p[i]);
            cnt_visit[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