제출 #1320132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320132		lucas110550	선물 (IOI25_souvenirs)	C++20	4 / 100	12 ms	400 KiB

souvenirs

#include <vector>
#include <algorithm>
#include <iostream>
#include "souvenirs.h"
using namespace std;

void buy_souvenirs(int N, long long P0) {
    // ------------------------------------------------------------
    // 1. Pre-compute Fibonacci numbers up to N+2.
    // ------------------------------------------------------------
    vector<long long> F;
    F.reserve(N + 3);
    F.push_back(0); // F[0]
    F.push_back(1); // F[1]
    
    for (int k = 2; k <= N + 2; ++k) {
        F.push_back(F.back() + F[F.size() - 2]);
    }

    // ------------------------------------------------------------
    // 2. Determine the prices P[1] ... P[N-2] by binary search.
    // ------------------------------------------------------------
    // P[0] is known. We allocate size N to store indices 0 to N-1.
    // Note: Python logic stops filling at P[N-2], so P[N-1] is unused/implicit.
    vector<long long> P(N); 
    P[0] = P0;

    for (int i = 1; i < N - 1; ++i) {
        long long prev = P[i - 1]; // price of the previous (more expensive) type
        int L = N - i + 1;         // length of the suffix
        
        // Python: low = (prev - F[L - 1]) // F[L]
        // C++ integer division behaves like // for positive numbers.
        long long low = (prev - F[L - 1]) / F[L];
        
        if (low < 1) {
            low = 1;
        }
        
        long long high = prev - 1;

        // Binary search
        while (low < high) {
            long long mid = low + (high - low) / 2;
            
            // Execute transaction
            pair<vector<int>, long long> res = transaction(mid);
            const vector<int>& bought = res.first;
            
            // Check if i is in bought
            bool found = false;
            for (int type : bought) {
                if (type == i) {
                    found = true;
                    break;
                }
            }

            if (found) {
                high = mid; // type i is bought -> try smaller M
            } else {
                low = mid + 1; // type i not bought -> need larger M
            }
        }
        P[i] = low;
    }

    // ------------------------------------------------------------
    // 3. First round of transactions
    // ------------------------------------------------------------
    vector<int> bought_cnt(N, 0);
    
    for (int i = 1; i < N; ++i) {
        long long M = P[i - 1] - 1;
        pair<vector<int>, long long> res = transaction(M);
        
        for (int t : res.first) {
            if (t < N) { // Bounds check safety
                bought_cnt[t]++;
            }
        }
    }

    // ------------------------------------------------------------
    // 4. Finish the collection
    // ------------------------------------------------------------
    
    // For types 1 ... N-2
    for (int i = 1; i < N - 1; ++i) {
        while (bought_cnt[i] < i) {
            transaction(P[i]); // buys exactly one souvenir of type i
            bought_cnt[i]++;
        }
    }

    // For smallest type (N-1)
    int last_type = N - 1;
    while (bought_cnt[last_type] < last_type) {
        // buys exactly one souvenir of the last type
        transaction(P[N - 2] - 1); 
        bought_cnt[last_type]++;
    }
}

• 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