Submission #1250644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250644		countless	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	12 ms	424 KiB

souvenirs

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

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

void buy_souvenirs(int N, ll P0) {
    vector<ll> vals(N, -1), sums(N, -1);
    vector<set<int>> queries(N);
    vector<int> cnt(N);
    vals[0] = P0;

    while (true) {
        int need = 0;
        for (int i = 0; i < N; i++) need += vals[i] == -1;
        if (need == 0) break;

        bool found = false;
        for (int i = N-1; i >= 0; i--) {
            if (vals[i] == -1) found = true;
            if (vals[i] != -1 and found) {
                // dame un grr
                auto [v, rem] = transaction(vals[i] - 1);
                set<int> st;
                for (auto &x : v) st.insert(x), cnt[x]++;
                ll val = vals[i] - 1 - rem;

                for (int j = 0; j < N; j++) {
                    if (vals[j] != -1 and st.count(j)) {
                        st.extract(j);
                        val -= vals[j];
                    }
                }

                int j = *st.begin();
                sums[j] = val;
                queries[j] = st;
                break;
            }

            if (queries[i].size() == 1) {
                vals[i] = sums[i];
                queries[i].clear();

                for (int j = 0; j < N; j++) {
                    if (queries[j].count(i)) {
                        sums[j] -= vals[i];
                        queries[j].extract(i);
                    }
                }
                break;
            }

            if (queries[i].size()) {
                // un que, un que?
                ll que = sums[i] / queries[i].size();
                auto [v, rem] = transaction(que);
                set<int> st;
                for (auto &x : v) st.insert(x), cnt[x]++;
                ll val = que - rem;

                for (int j = 0; j < N; j++) {
                    if (vals[j] != -1 and st.count(j)) {
                        st.extract(j);
                        val -= vals[j];
                    }
                }

                int j = *st.begin();
                sums[j] = val;
                queries[j] = st;
                break;
            }
        }
    }

    for (int i = 1; i < N; i++) {
        while (cnt[i] < i) {
            auto res = transaction(vals[i]);
            cnt[i]++;
        }
    }
    return;
}
// see messy sol on qoj
// this is so clean ty dom

• 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