Submission #1254709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254709		lorpu	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	13 ms	420 KiB

souvenirs

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

void buy_souvenirs(int N, long long P0) {
    vector<long long> p(N, -1);
    p[0] = P0;

    vector<int> calls(N, 0);

    function<void(long long)> solve = [&](long long c) {
        long long sp = c - 1;
        std::pair<std::vector<int>, long long> res = transaction(sp);
        sp -= res.second;
        for (int s : res.first) calls[s]++;

        vector<int> sv = res.first;

        while (true) {
            for (int i = 0; i < sv.size();) {
                if (p[sv[i]] != -1) {
                    sp -= p[sv[i]];
                    sv.erase(sv.begin() + i);
                    continue;
                }
                i++;
            }
            if (sv.size() == 1) {
                p[sv[0]] = sp;
                if (sv[0] < N - 1 && p[sv[0] + 1] == -1) solve(sp);
                break;
            }

            solve(sp / sv.size() + 1);
        }
    };

    for (int i = 1; i < N; i++) {
        if (p[i] == -1) solve(p[i - 1]);
    }

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