Submission #1249394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249394		mondellbit	Souvenirs (IOI25_souvenirs)	C++20	0 / 100	0 ms	408 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>

using namespace std;

vector<long long> P;
vector<int> bought_counts;

pair<vector<int>, long long> transaction(long long M);

void buy_souvenirs(int N, long long P0) {
    vector<long long> prices(N);
    vector<int> counts(N, 0);
    prices[0] = P0;

    for (int i = N - 1; i >= 1; --i) {
        long long low = (i == N - 1) ? 1 : prices[i + 1] + 1;
        long long high = prices[0] - 1;
        long long candidate = high + 1;

        while (low <= high) {
            long long mid = low + (high - low) / 2;
            try {
                pair<vector<int>, long long> outcome = transaction(mid);
                vector<int> L = outcome.first;
                bool found_i = false;
                for (int type : L) {
                    if (type == i) {
                        found_i = true;
                    }
                    if (counts[type] < type) {
                        counts[type]++;
                        bought_counts[type]++;
                    }
                }
                if (found_i) {
                    candidate = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } catch (...) {
                low = mid + 1;
            }
        }

        if (candidate > prices[0] - 1) {
            candidate = low;
            try {
                pair<vector<int>, long long> outcome = transaction(candidate);
                vector<int> L = outcome.first;
                for (int type : L) {
                    if (counts[type] < type) {
                        counts[type]++;
                        bought_counts[type]++;
                    }
                }
            } catch (...) {
                candidate = low + 1;
                try {
                    pair<vector<int>, long long> outcome = transaction(candidate);
                    vector<int> L = outcome.first;
                    for (int type : L) {
                        if (counts[type] < type) {
                            counts[type]++;
                            bought_counts[type]++;
                        }
                    }
                } catch (...) {
                }
            }
        }
        prices[i] = candidate;
    }

    for (int i = 1; i < N; ++i) {
        int need = i - counts[i];
        for (int j = 0; j < need; ++j) {
            try {
                pair<vector<int>, long long> outcome = transaction(prices[i]);
                vector<int> L = outcome.first;
                for (int type : L) {
                    if (counts[type] < type) {
                        counts[type]++;
                        bought_counts[type]++;
                    }
                }
            } catch (...) {
            }
        }
    }
}

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