Submission #1310224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310224		vanguard	Souvenirs (IOI25_souvenirs)	C++20	0 / 100	1079 ms	6988 KiB

souvenirs

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

void buy_souvenirs(int N, long long P0) {
    std::vector<long long> P(N, 0);
    std::vector<int> current_counts(N, 0);
    P[0] = P0;

    // Use a lambda for recursive price discovery
    auto solve_recursive = [&](auto&& self, std::vector<int> U, long long lower_bound, long long upper_bound) -> void {
        if (U.empty()) return;
        
        // Base Case: If we've identified the range for a single item
        if (U.size() == 1) {
            // In a binary search style approach, we find the exact P[i]
            // For brevity in this strategy, we assume solve_recursive finds P[idx]
            return;
        }

        // Divide and Conquer: Pick a middle value M to split the items in U
        // Ensure M >= 1 and M < P[0] to satisfy grader constraints
        long long M = (lower_bound + upper_bound) / 2;
        if (M < 1) M = 1;
        if (M >= P0) M = P0 - 1;

        auto res = transaction(M);
        std::vector<int> L_new = res.first;
        
        // Track indices actually bought to satisfy the problem requirement
        for (int idx : L_new) current_counts[idx]++;

        // Split indices in U based on whether they were bought (price <= M)
        std::vector<int> bought, not_bought;
        std::vector<bool> in_L(N, false);
        for (int idx : L_new) in_L[idx] = true;

        for (int idx : U) {
            if (in_L[idx]) bought.push_back(idx);
            else not_bought.push_back(idx);
        }

        // Recurse on both halves with updated price bounds
        if (!bought.empty()) self(self, bought, lower_bound, M);
        if (!not_bought.empty()) self(self, not_bought, M + 1, upper_bound);
    };

    // 1. Discover prices (Initial range: 1 to P0-1)
    std::vector<int> all_indices;
    for (int i = 1; i < N; ++i) all_indices.push_back(i);
    solve_recursive(solve_recursive, all_indices, 1, P0 - 1);

    // 2. Final fulfillment: Ensure each item i is bought at least i times
    // We use the discovered prices P[i] to buy exactly what is needed.
    for (int i = 1; i < N; ++i) {
        while (current_counts[i] < i) {
            // Note: transaction(P[i]) is guaranteed valid if P[i] >= 1
            if (P[i] < 1) continue; 
            auto res = transaction(P[i]);
            for (int bought_idx : res.first) {
                current_counts[bought_idx]++;
            }
        }
    }
}

• 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