Submission #1262594

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

souvenirs

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

using i32 = int32_t;
#define int long long

int p[101], cnt[101];
pair<set<int>, int> e[101];

void buy_souvenirs(i32 N, int P0) {
    int cur = P0 - 1, smol = 0;
    while (smol < N - 1) {
        auto [vec, c] = transaction(cur);
        c = cur - c;
        smol = vec[0];
        set<int> temp;
        for (auto& x : vec) temp.insert(x), cnt[x]++;
        e[smol] = {temp, c};
        if (smol == N - 1) {
            p[N - 1] = c;
            for (int i = 1; i < N; i++) if (e[i].first.count(N - 1)) e[i].second -= c, e[i].first.erase(N - 1);
        } else if (temp.size() == 1) cur = c - 1;
        else cur = c / temp.size();
    }
    for (int i = N - 2; i >= 1; i--) {
        if (!e[i].first.empty()) {
            p[i] = e[i].second;
            for (int k = 1; k < N; k++) if (e[k].first.count(i)) e[k].second -= p[i], e[k].first.erase(i);
        } else {
            int j;
            for (j = i; j >= 1; j--) if (!e[j].first.empty()) break;
            if (e[j].first.size() == 1) cur = e[j].second - 1;
            else cur = e[j].second / e[j].first.size();
            while (j < i) {
                auto [vec, c] = transaction(cur);
                c = cur - c;
                j = vec[0];
                set<int> temp;
                for (auto& x : vec) {
                    cnt[x]++;
                    if (p[x] != 0) c -= p[x];
                    else temp.insert(x);
                }
                e[j] = {temp, c};
                if (j == i) {
                    p[i] = c;
                    for (int k = 1; k < N; k++) if (e[k].first.count(i)) e[k].second -= c, e[k].first.erase(i);
                } else if (temp.size() == 1) cur = c - 1;
                else cur = c / temp.size();
            }
        }
    }
    for (int i = 1; i < N; i++) while (cnt[i] < i) transaction(p[i]), cnt[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