제출 #1339202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1339202		Desh03	선물 (IOI25_souvenirs)	C++20	25 / 100	13 ms	412 KiB

souvenirs

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

using namespace std;

void buy_souvenirs(int n, long long p0) {
    auto [x, y] = transaction(p0 - 1);
    vector<pair<long long, vector<int>>> q = {{p0 - 1 - y, x}};
    vector<long long> ans(n);
    vector<int> cnt(n);
    for (int t : x) {
        ++cnt[t];
    }
    ans[0] = p0;
    while (count(ans.begin(), ans.end(), 0)) {
        if (q.empty()) {
            for (int i = n - 2; i >= 0; i--) {
                if (ans[i] && !ans[i + 1]) {
                    auto [x, y] = transaction(ans[i] - 1);
                    for (int t : x) {
                        ++cnt[t];
                    }
                    vector<int> nv;
                    long long s = 0, c = ans[i] - 1 - y;
                    for (int j = 0; j < x.size(); j++) {
                        if (!ans[x[j]]) {
                            nv.push_back(x[j]);
                        } else {
                            c -= ans[x[j]];
                        }
                    }
                    q.push_back({c, nv});
                    break;
                }
            }
        }
        auto it = min_element(q.begin(), q.end());
        if (it == q.end()) {
            transaction(p0);
        }
        if ((*it).first == 0) {
            q.erase(it);
            continue;
        }
        auto [a, b] = *it;
        if (b.size() == 1) {
            ans[b[0]] = a;
            for (int j = 0; j < q.size(); j++) {
                auto it = find(q[j].second.begin(), q[j].second.end(), b[0]);
                if (it != q[j].second.end()) {
                    q[j].second.erase(it);
                    q[j].first -= a;
                }
            }
        } else {
            auto [b2, a2] = transaction(a / b.size());
            for (int t : b2) {
                ++cnt[t];
            }
            vector<int> nv;
            long long c = a / b.size() - a2;
            for (int j = 0; j < b2.size(); j++) {
                if (!ans[b2[j]]) {
                    nv.push_back(b2[j]);
                } else {
                    c -= ans[b2[j]];
                }
            }
            q.push_back({c, nv});
        }
    }
    for (int i = 0; i < n; i++) {
        while (cnt[i] < i) {
            transaction(ans[i]);
            ++cnt[i];
        }
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 4 / 4
• Subtask 2: 3 / 3
• Subtask 3: 0 / 14
• Subtask 4: 18 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33