제출 #1252168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252168		EJIC_B_KEDAX	선물 (IOI25_souvenirs)	C++20	100 / 100	12 ms	424 KiB

souvenirs

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

using namespace std;
using ll = long long;

void buy_souvenirs(int n, ll p0) {
    int target = n - 1;
    vector<int> cnt(n, 0);
    vector<ll> cost(n, -1);
    vector<vector<int>> resp(n);
    vector<ll> respc(n, 0);
    cost[0] = p0;
    resp[0] = {0};
    respc[0] = p0;
    int cur = 0;
    auto get_next = [](int cnt, ll cost) -> ll {
        if (cnt == 1) return cost - 1;
        return cost / cnt;
    };
    while (target != 0) {
        while (cur != target) {
            ll coins = get_next(resp[cur].size(), respc[cur]);
            auto [vec, rem] = transaction(coins);
            for (int i : vec) {
                cnt[i]++;
            }
            resp[vec[0]] = vec;
            respc[vec[0]] = coins - rem;

            for (int i = 0; i < vec.size(); i++) {
                if (cost[vec[i]] != -1) {
                    respc[vec[0]] -= cost[vec[i]];
                    resp[vec[0]].erase(ranges::find(resp[vec[0]], vec[i]));
                }
            }
            if (resp[vec[0]].size() == 1) {
                cost[vec[0]] = respc[vec[0]];
            }

            cur = vec[0];
        }
        for (int j = n - 1; j >= 0; j--) {
            for (int i = 1; i < resp[j].size(); i++) {
                if (cost[resp[j][i]] != -1) {
                    respc[j] -= cost[resp[j][i]];
                    resp[j].erase(resp[j].begin() + i);
                    i--;
                }
            }
            if (resp[j].size() == 1) {
                cost[j] = respc[j];
            }
        }
        while (target && cost[target] != -1) {
            target--;
        }
        cur = target;
        while (resp[cur].empty()) {
            cur--;
        }
    }
    for (int i = 0; i < n; i++) {
        while (cnt[i] != i) {
            transaction(cost[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