Submission #1256315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256315		arafatbot144	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	13 ms	428 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

using vi = vector<int>;
using ll = long long;

#define fst first
#define snd second

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

pair<vi, ll> transaction(ll M);

void buy_souvenirs(int N, ll P0) {
    vector<ll> total(N);
    vector<vi> types(N);
    vector<bool> vis(N);
    vi need(N);
    iota(all(need), 0);
    auto query = [&](ll M) {
        auto [L, R] = transaction(M);
        for (int x : L) need[x]--;
        return pair<ll, vi>{M - R, L};
    };
    total[0] = P0, types[0] = {0}, vis[0] = true;
    dforn(i, N) {
        int j = i;
        while (!vis[j]) j--;
        while (true) {
            while (types[j].back() > i) {
                assert(sz(types[types[j].back()]) == 1);
                total[j] -= total[types[j].back()];
                types[j].pop_back();
            }
            if (j == i) break;
            assert(j < i);
            int C = sz(types[j]);
            ll P = C == 1 ? total[j] - 1 : total[j] / C;
            auto ret = query(P);
            j = ret.snd.front();
            tie(total[j], types[j]) = ret, vis[j] = true;
        }
    }
    forn(i, N) while (need[i]) {
        query(total[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