Submission #1249393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249393		mondellbit	Souvenirs (IOI25_souvenirs)	C++20	Compilation error	0 ms	0 KiB

souvenirs

#include "souvenirs.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <utility>
#include <stdexcept>

using namespace std;

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

pair<vector<int>, long long> transaction(long long M) {
    vector<int> bought;
    long long remaining = M;
    for (int i = 0; i < P.size(); ++i) {
        if (remaining >= P[i]) {
            remaining -= P[i];
            bought.push_back(i);
        }
    }
    return {bought, remaining};
}

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 (...) {
            }
        }
    }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccNHwK81.o: in function `transaction(long long)':
stub.cpp:(.text+0x1d0): multiple definition of `transaction(long long)'; /tmp/ccqYgyWv.o:souvenirs.cpp:(.text+0x0): first defined here
collect2: error: ld returned 1 exit status