Submission #1251226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251226		bronze_coder	Festival (IOI25_festival)	C++20	Compilation error	0 ms	0 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> max_coupons(long long A, vector<int> P, vector<int> T){
    int subtask = 3;
    int n = P.size();
    for(int i=0;i<n;i++){
        if(T[i]>2){
            subtask = 5;
        }
    }
    if(n<=70){
        subtask = 4;
    }
    vector<pair<int,int>> l1;
    vector<pair<int,int>> l2;
    vector<pair<int,int>> l3;
    vector<pair<int,int>> l4;
    for(int i=0;i<n;i++){
        if(T[i]==1){
            l1.push_back({P[i],i});
        }
        if(T[i]==2){
            l2.push_back({P[i],i});
        }
        if(T[i]==3){
            l3.push_back({P[i],i});
        }
        if(T[i]==4){
            l4.push_back({P[i],i});
        }
    }
    sort(l1.begin(),l1.end());
    sort(l2.begin(),l2.end());
    sort(l3.begin(),l3.end());
    sort(l4.begin(),l4.end());
    if(subtask==3){
        vector<int> prefix = {0};
        for(int i=0;i<l1.size();i++){
            prefix.push_back(prefix[i]+l1[i].first);
        }
        long long A1 = A;
        int ans = 0;
        for(int i=0;i<=l2.size();i++){
            if(i!=0){
                A -= l2[i-1].first;
                A *= 2;
                A = min(A,1000000000000000);
            }
            int low = 0;
            int high = prefix.size()-1;
            while(low<high){
                int mid = (low+high+1)/2;
                if(prefix[mid]>A){
                    high = mid-1;
                }
                else{
                    low = mid;
                }
            }
            ans = max(ans,i+low);
            if(A<0){
                break;
            }
        }

        A = A1;
        for(int i=0;i<=l2.size();i++){
            if(i!=0){
                A -= l2[i-1].first;
                A *= 2;
                A = min(A,1000000000000000);
            }
            int low = 0;
            int high = prefix.size()-1;
            while(low<high){
                int mid = (low+high+1)/2;
                if(prefix[mid]>A){
                    high = mid-1;
                }
                else{
                    low = mid;
                }
            }
            if(ans==i+low){
                vector<int> answer;
                for(int j=0;j<i;j++){
                    answer.push_back(l2[j].second);
                }
                for(int j=0;j<low;j++){
                    answer.push_back(l1[j].second);
                }
                return answer;
            }
        }
    }
    if(subtask==4){
        vector<pair<int,int>> l;
        for(int i=0;i<n;i++){
            if(T[i]!=1){
                l.push_back({1LL*T[i]*P[i]*(6/(T[i]-1)),i});
            }
        }
        sort(l.begin(),l.end());
        for(int i=0;i<l1.size();i++){
            l.push_back(l1[i]);
        }
        vector<int> ans;
        for(int i=0;i<n;i++){
            ans.push_back(l[i].second);
        }
        long long dp[n+1][n+1];
        int f[n+1][n+1];
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                if(i==0){
                    if(j==0){
                        dp[i][j] = A;
                    }
                    else{
                        dp[i][j] = -1;
                    }
                }
                else{
                    long long x;
                    if(j>=1){
                        x = (dp[i-1][j-1]-P[ans[i-1]])*T[ans[i-1]];
                    } 
                    else{
                        x = -1;
                    }
                    if(x>dp[i-1][j]){
                        dp[i][j] = x;
                        f[i][j] = 1;
                    }
                    else{
                        dp[i][j] = dp[i-1][j];
                        f[i][j] = 0;
                    }
                    dp[i][j] = min(dp[i][j],1000000000000000);
                }
            }
        }

        for(int i=n;i>=0;i--){
            vector<int> answer;
            if(dp[n][i]>=0){
                for(int j=n;j>0;j--){
                    if(f[j][i]){
                        answer.push_back(ans[j-1]);
                        i--;
                    }
                }
                vector<int> answer1;
                for(int j=0;j<answer.size();j++){
                    answer1.push_back(answer[answer.size()-1-j]);
                }
                return answer1;
            }
        }
    }
    if(subtask==5){
        vector<pair<int,int>> l;
        for(int i=0;i<n;i++){
            if(T[i]!=1){
                l.push_back({1LL*T[i]*P[i]*(6/(T[i]-1)),i});
            }
        }
        sort(l.begin(),l.end());
        for(int i=0;i<l1.size();i++){
            l.push_back(l1[i]);
        }
        vector<int> ans;
        for(int i=0;i<n;i++){
            ans.push_back(l[i].second);
        }
        return ans;
    }
}

Compilation message (stderr)

festival.cpp: In function 'std::vector<int> max_coupons(long long int, std::vector<int>, std::vector<int>)':
festival.cpp:49:24: error: no matching function for call to 'min(long long int&, long int)'
   49 |                 A = min(A,1000000000000000);
      |                     ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from festival.h:1,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
festival.cpp:49:24: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'long int')
   49 |                 A = min(A,1000000000000000);
      |                     ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from festival.h:1,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
festival.cpp:49:24: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'long int')
   49 |                 A = min(A,1000000000000000);
      |                     ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from festival.h:1,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3449 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3449:5: note:   template argument deduction/substitution failed:
festival.cpp:49:24: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   49 |                 A = min(A,1000000000000000);
      |                     ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from festival.h:1,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3455 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3455:5: note:   template argument deduction/substitution failed:
festival.cpp:49:24: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   49 |                 A = min(A,1000000000000000);
      |                     ~~~^~~~~~~~~~~~~~~~~~~~
festival.cpp:73:24: error: no matching function for call to 'min(long long int&, long int)'
   73 |                 A = min(A,1000000000000000);
      |                     ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from festival.h:1,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
festival.cpp:73:24: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'long int')
   73 |                 A = min(A,1000000000000000);
      |                     ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from festival.h:1,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
festival.cpp:73:24: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'long int')
   73 |                 A = min(A,1000000000000000);
      |                     ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from festival.h:1,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3449 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3449:5: note:   template argument deduction/substitution failed:
festival.cpp:73:24: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   73 |                 A = min(A,1000000000000000);
      |                     ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from festival.h:1,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3455 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3455:5: note:   template argument deduction/substitution failed:
festival.cpp:73:24: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   73 |                 A = min(A,1000000000000000);
      |                     ~~~^~~~~~~~~~~~~~~~~~~~
festival.cpp:141:35: error: no matching function for call to 'min(long long int&, long int)'
  141 |                     dp[i][j] = min(dp[i][j],1000000000000000);
      |                                ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from festival.h:1,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
festival.cpp:141:35: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'long int')
  141 |                     dp[i][j] = min(dp[i][j],1000000000000000);
      |                                ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from festival.h:1,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
festival.cpp:141:35: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'long int')
  141 |                     dp[i][j] = min(dp[i][j],1000000000000000);
      |                                ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from festival.h:1,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3449 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3449:5: note:   template argument deduction/substitution failed:
festival.cpp:141:35: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  141 |                     dp[i][j] = min(dp[i][j],1000000000000000);
      |                                ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from festival.h:1,
                 from festival.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3455 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3455:5: note:   template argument deduction/substitution failed:
festival.cpp:141:35: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  141 |                     dp[i][j] = min(dp[i][j],1000000000000000);
      |                                ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
festival.cpp:180:1: warning: control reaches end of non-void function [-Wreturn-type]
  180 | }
      | ^