Submission #1258515

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

souvenirs

#include <iostream>
#include <vector>
#include <set>
#define int long long
using namespace std;
struct comp{
    bool operator()(pair<set<int32_t>, int> a, pair<set<int32_t>, int> b) const {
        return *a.first.begin() > *b.first.begin();
    }
};
pair<vector<int32_t>, int> transaction(int m);
pair<set<int32_t>, int> equate(vector<int32_t>& idx, int l, int o, vector<int>& cnt) {
    set<int32_t> f;
    for (auto x : idx) f.insert(x), ++cnt[x];
    return make_pair(f, o - l);
}
void buy_souvenirs(int32_t n, int p0) {
    auto r = transaction(p0 - 1);
    set<pair<set<int32_t>, int>, comp> s;
    vector<int> p(n, -1), cnt(n, 0);
    set<int32_t> u;
    for (int i = 1; i < n; ++i) u.insert(i);
    s.insert(equate(r.first, r.second, p0 - 1, cnt));
    while (s.size() && u.size()) {
        auto c = *s.begin();
        vector<int> rm;
        for (auto x : c.first)
            if (p[x] != -1)
                rm.push_back(x);
        for (auto x : rm)
            c.first.erase(x),
            c.second -= p[x];
        if (c.first.size() > 1) {
            int nxt = c.second / c.first.size();
            r = transaction(nxt);
            s.insert(equate(r.first, r.second, nxt, cnt));
        }
        else {
            int idx = *c.first.begin();
            u.erase(idx);
            p[idx] = c.second;
            s.erase(s.begin());
            if (!u.size()) break;
            if (*u.rbegin() > idx) {
                int nxt = c.second - 1;
                r = transaction(nxt);
                s.insert(equate(r.first, r.second, nxt, cnt));
            }
        }
    }
    for (int i = 1; i < n; ++i)
        for (int j = cnt[i]; j < i; ++j)
            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