제출 #1273402

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273402		AksLolCoding	선물 (IOI25_souvenirs)	C++17	100 / 100	13 ms	404 KiB

souvenirs

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

const int maxn = 105;

struct result {
    vector<int> items;
    ll price = 0;
};

result leading[maxn];
ll prices[maxn];
int bought[maxn];
int known_leading;

result add_leading(ll curp) {
    auto [items, price] = transaction(curp);
    sort(items.begin(), items.end());
    if (leading[items[0]].price == 0) known_leading++;
    leading[items[0]] = {items, curp - price};
    for (int i : items) bought[i]++;
    return {items, price};
}

void calc_price(int i) {
    ll me = leading[i].price;
    for (int j : leading[i].items) if (j != i) me -= prices[j];
    prices[i] = me;
}

void buy_souvenirs(int n, ll P0) {
    ll curp = P0 - 1;
    fill(leading, leading+maxn, result());

    // create equations
    while (true) {
        auto [items, price] = add_leading(curp);
        int k = items.size();
        curp -= price;
        curp /= k;
        if (k == 1) curp--;
        if (items[0] == n-1) break; 
    }

    // solve equations
    while (known_leading < n-1) {
        int unknown = n-1;
        while (leading[unknown].price) {
            if (!prices[unknown]) calc_price(unknown);
            unknown--;
        }   
        int known = unknown;
        while (leading[known].price == 0) known--;
        ll totalp = leading[known].price;
        int totaln = leading[known].items.size();
        for (int j : leading[known].items) {
            if (j > unknown) {
                if (!prices[j]) calc_price(j);
                totaln--;
                totalp -= prices[j];
            }
        }

        totalp /= totaln;
        if (totaln == 1) totalp--;
        auto [items, price] = add_leading(totalp);
        int cnt_unknown = items.size();
        ll total = totalp - price;
        for (int i : items) {
            if (prices[i]) {
                total -= prices[i];
                cnt_unknown--;
            }
        }
        if (cnt_unknown == 1) prices[items[0]] = total;
    }

    // make purchases
    for (int i = n-1; i >= 0; i--) {
        calc_price(i);
        while (bought[i] < i) {
            transaction(prices[i]);
            bought[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