Submission #1275981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275981		sphoabinh1980	선물 (IOI25_souvenirs)	C++20	0 / 100	1071 ms	332 KiB

souvenirs

#include "souvenirs.h"
#include <vector>
#include <algorithm>
#include <functional>  // <-- THÊM DÒNG NÀY
using namespace std;

void buy_souvenirs(int N, long long P0) {
    // Sinh tất cả dãy P khả dĩ
    vector<vector<int>> candidates;
    vector<int> cur = { (int)P0 };
    
    // Đổi tên từ 'generate' → 'gen' để tránh xung đột
    function<void()> gen = [&]() {
        if ((int)cur.size() == N) {
            candidates.push_back(cur);
            return;
        }
        int last = cur.back();
        for (int x = last - 1; x >= 1; --x) {
            cur.push_back(x);
            gen();  // gọi đệ quy chính nó
            cur.pop_back();
        }
    };
    gen();  // khởi chạy

    vector<int> total_bought(N, 0);

    // Lọc dần các candidate bằng truy vấn
    while (candidates.size() > 1) {
        bool found_M = false;
        for (long long M = 1; M < P0; ++M) {
            // Mô phỏng transaction(M) trên tất cả candidate
            vector<vector<int>> results;
            for (auto& cand : candidates) {
                long long coins = M;
                vector<int> bought;
                for (int i = 0; i < N; ++i) {
                    if (coins >= cand[i]) {
                        coins -= cand[i];
                        bought.push_back(i);
                    }
                }
                results.push_back(bought);
            }

            // Kiểm tra có phân biệt được không
            bool all_same = true;
            for (int i = 1; i < (int)results.size(); ++i) {
                if (results[i] != results[0]) {
                    all_same = false;
                    break;
                }
            }
            if (!all_same) {
                // Gọi transaction thật
                auto real_res = transaction(M);
                const vector<int>& real_bought = real_res.first;
                for (int t : real_bought) {
                    total_bought[t]++;
                }

                // Lọc candidate khớp với kết quả thật
                vector<vector<int>> new_candidates;
                for (int i = 0; i < (int)candidates.size(); ++i) {
                    if (results[i] == real_bought) {
                        new_candidates.push_back(candidates[i]);
                    }
                }
                candidates = new_candidates;
                found_M = true;
                break;
            }
        }
        if (!found_M) break; // không còn M nào phân biệt được
    }

    // Mua đủ số lượng còn thiếu
    vector<int> P = candidates[0];
    for (int i = 1; i < N; ++i) {
        int need = i - total_bought[i];
        for (int j = 0; j < need; ++j) {
            transaction(P[i]);
        }
    }
}

• 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