Submission #1253062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253062		TheScrasse	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	13 ms	436 KiB

souvenirs

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

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 110

#include "souvenirs.h"
#include <utility>
#include <vector>

void buy_souvenirs(int N, long long P0) {
    // full
    vector<ll> P(N, -1), rem(N, 0);
    iota(rem.begin(), rem.end(), 0);
    P[0] = P0;

    map<ll, pair<vector<int>, array<ll, 2>>> starts;
    auto trans = [&](ll M, bool flag = true) {
        auto [v, rem_money] = transaction(M);

        /* cerr << "trans" _ M << nf;
        for (auto u : v) cerr << u << ' ';
        cerr << nf; */

        for (auto u : v) rem[u]--;
        pair<vector<int>, ll> ans = {v, rem_money};
        if (flag) assert(starts.find(v[0]) == starts.end());
        starts[v[0]] = {v, {M, rem_money}};
        return ans;
    };

    auto clean = [&](pair<vector<int>, array<ll, 2>> ans) {
        auto [v, info] = ans;
        vector<int> w;
        for (auto u : v) {
            if (P[u] != -1) info[1] += P[u];
            else w.pb(u);
        }

        return pair<vector<int>, array<ll, 2>>{w, info};
    };

    trans(P[0] - 1);
    while (true) {
        ll mx = -1;
        for (ll i = N - 1; i >= 0; i--) {
            if (starts.find(i) != starts.end()) {
                mx = i; break;
            }
        }

        if (mx == -1) break;

        assert(mx != -1);
        starts[mx] = clean(starts[mx]);
        auto [v, info] = starts[mx];

        /* cout << "mx, info =" _ mx _ info[0] - info[1] << nf;
        for (auto u : v) cout << u << ' ';
        cout << nf; */

        if (v.size() == 1) {
            starts.erase(mx);
            P[mx] = info[0] - info[1];
            if (mx != N - 1 && P[mx + 1] == -1) trans(P[mx] - 1);
        } else {
            trans((info[0] - info[1]) / v.size());
        }
    }

    /* for (ll i = 0; i < N; i++) cerr << P[i] << ' ';
    cerr << nf; */

    for (ll i = 1; i < N; i++) {
        while (rem[i] != 0) {
            trans(P[i], false);
        }
    }
}

• 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