Submission #1275980

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

souvenirs

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

void buy_souvenirs(int N, long long P0) {
    // Sinh tất cả dãy P khả dĩ: giảm dần, P[0]=P0, 1<=P[i]<=10
    vector<vector<int>> candidates;
    vector<int> cur = { (int)P0 };
    
    function<void()> generate = [&]() {
        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);
            generate();
            cur.pop_back();
        }
    };
    generate();

    vector<int> total_bought(N, 0);

    // Duyệt để xác định đúng dãy P
    while (candidates.size() > 1) {
        // Chọn M = 1 (luôn an toàn vì P[N-1] >= 1, và nếu không mua -> skip, nhưng đề bài cấm)
        // Thay vào đó, chọn M = P0 - 1 (luôn >= P[N-1])
        long long M = P0 - 1;
        // Nhưng để phân biệt, chọn M nhỏ nhất có thể phân biệt các candidate
        // Đơn giản: thử M = 1,2,...,P0-1 đến khi phân biệt được
        bool found = false;
        for (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 xem có ít nhất 2 kết quả khác nhau
            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) {
                // Dùng M này để truy vấn thật
                auto real_res = transaction(M);
                const vector<int>& real_bought = real_res.first;
                // Cập nhật total_bought
                for (int t : real_bought) {
                    total_bought[t]++;
                }
                // Lọc candidates
                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 = true;
                break;
            }
        }
        if (!found) break;
    }

    // Bây giờ candidates[0] là dãy P đúng
    vector<int> P = candidates[0];

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

Compilation message (stderr)

souvenirs.cpp: In function 'void buy_souvenirs(int, long long int)':
souvenirs.cpp:11:5: error: 'function' was not declared in this scope
   11 |     function<void()> generate = [&]() {
      |     ^~~~~~~~
souvenirs.cpp:4:1: note: 'std::function' is defined in header '<functional>'; did you forget to '#include <functional>'?
    3 | #include <algorithm>
  +++ |+#include <functional>
    4 | using namespace std;
souvenirs.cpp: In lambda function:
souvenirs.cpp:19:21: error: no matching function for call to 'generate()'
   19 |             generate();
      |             ~~~~~~~~^~
In file included from /usr/include/c++/13/algorithm:61,
                 from souvenirs.cpp:3:
/usr/include/c++/13/bits/stl_algo.h:4434:5: note: candidate: 'template<class _FIter, class _Generator> constexpr void std::generate(_FIter, _FIter, _Generator)'
 4434 |     generate(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:4434:5: note:   template argument deduction/substitution failed:
souvenirs.cpp:19:21: note:   candidate expects 3 arguments, 0 provided
   19 |             generate();
      |             ~~~~~~~~^~
In file included from /usr/include/c++/13/algorithm:73:
/usr/include/c++/13/pstl/glue_algorithm_defs.h:200:1: note: candidate: 'template<class _ExecutionPolicy, class _ForwardIterator, class _Generator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> std::generate(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Generator)'
  200 | generate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Generator __g);
      | ^~~~~~~~
/usr/include/c++/13/pstl/glue_algorithm_defs.h:200:1: note:   template argument deduction/substitution failed:
souvenirs.cpp:19:21: note:   candidate expects 4 arguments, 0 provided
   19 |             generate();
      |             ~~~~~~~~^~
souvenirs.cpp: In function 'void buy_souvenirs(int, long long int)':
souvenirs.cpp:23:13: error: no matching function for call to 'generate()'
   23 |     generate();
      |     ~~~~~~~~^~
/usr/include/c++/13/bits/stl_algo.h:4434:5: note: candidate: 'template<class _FIter, class _Generator> constexpr void std::generate(_FIter, _FIter, _Generator)'
 4434 |     generate(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:4434:5: note:   template argument deduction/substitution failed:
souvenirs.cpp:23:13: note:   candidate expects 3 arguments, 0 provided
   23 |     generate();
      |     ~~~~~~~~^~
/usr/include/c++/13/pstl/glue_algorithm_defs.h:200:1: note: candidate: 'template<class _ExecutionPolicy, class _ForwardIterator, class _Generator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> std::generate(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Generator)'
  200 | generate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Generator __g);
      | ^~~~~~~~
/usr/include/c++/13/pstl/glue_algorithm_defs.h:200:1: note:   template argument deduction/substitution failed:
souvenirs.cpp:23:13: note:   candidate expects 4 arguments, 0 provided
   23 |     generate();
      |     ~~~~~~~~^~