Submission #1300664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300664		thorbeam	Souvenirs (IOI25_souvenirs)	C++20	4 / 100	13 ms	332 KiB

souvenirs

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

typedef long long ll;

using namespace std;

void buy_souvenirs(int N, ll p0) {
    vector<int> bought(N, 0);
    vector<ll> known_price(N, 0);
    vector<pair<vector<int>, ll>> completed_transactions;
    vector<ll> money_unaccouted_for;

    auto purchase = transaction(p0 - 1);
    for (auto souvernir : purchase.first) {
        bought[souvernir]++;
    }
    completed_transactions.push_back(purchase);
    money_unaccouted_for.push_back(p0 - purchase.second);

    while (completed_transactions.back().first[0] != N - 1) {
        ll next_transaction = (money_unaccouted_for.back() - 1) /
                              completed_transactions.back().first.size();
        purchase = transaction(next_transaction);
        for (auto souvernir : purchase.first) {
            bought[souvernir]++;
        }
        completed_transactions.push_back(purchase);
        money_unaccouted_for.push_back(next_transaction - purchase.second);
    }

    known_price[N - 1] = money_unaccouted_for.back();
    completed_transactions.pop_back();
    money_unaccouted_for.pop_back();

    int next_price_to_find = N - 2;
    while (next_price_to_find != 0) {
        auto &last_price = money_unaccouted_for.back();
        auto &last_souvernirs = completed_transactions.back().first;

        // removes knwon prices
        for (int i = last_souvernirs.size(); i >= 0; i--) {
            auto souvernir = last_souvernirs[i];
            if (known_price[souvernir] != 0) {
                last_price -= known_price[souvernir];
                last_souvernirs.pop_back();
            } else {
                break;
            }
        }

        // checks if the first element is the next price to find
        // this means that the size must be 1
        // and the only one left is next price to find
        if (last_souvernirs[0] != next_price_to_find) {
            ll next_transaction = (money_unaccouted_for.back() - 1) /
                                  completed_transactions.back().first.size();
            purchase = transaction(next_transaction);
            for (auto souvernir : purchase.first) {
                bought[souvernir]++;
            }
            completed_transactions.push_back(purchase);
            money_unaccouted_for.push_back(next_transaction - purchase.second);
        } else {
            known_price[next_price_to_find] = money_unaccouted_for.back();
            completed_transactions.pop_back();
            money_unaccouted_for.pop_back();
        }
    }

    // completes remaining purchaces
    for (int i = 0; i < N; i++) {
        while (bought[i] < i) {
            transaction(known_price[i]);
        }
    }
}

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