Submission #1286144

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

festival

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

long long MX=1e15;

long long fnd(vector <long long>& k, long long num){
    
    long long l=0;
    long long r=k.size()-1;
    
    if (num >= k[r]) return r;

    while (l<r) {
        long long md=(l+r+1)/2;
        if (k[md]<=num)
            l=md;     
        else
            r=md-1;  
    }
    return l;
}

vector<int> max_coupons(int A,vector<int> P,vector <int> T){
    
    vector <pair<long long,long long>> vp1;
    vector <pair<long long,long long>> vp2;
    vector <pair<long long,long long>> vp3;
    vector <pair<long long,long long>> vp4;
     
    for (int i=0; i<P.size(); i++){
        if (T[i]==1){vp1.push_back(P[i],i)};
        if (T[i]==2){vp2.push_back(P[i],i)};
        if (T[i]==3){vp3.push_back(P[i],i)};
        if (T[i]==4){vp4.push_back(P[i],i)};
    } 
    
    if (vp2.size()==0 && vp3.size()==0 && vp4.size()==0){
    //subtask 1 / 5 points / T[i] = 1 for each i such that 0 ≤ i < N
    //for subtask 1 it is clear that we should sort and just do some o(n) solution.
    
    sort(vp1.begin(),vp1.end());vector <int> ans;int k=0;
    while (A>=0 && k<vp1.size()){A=A-vp[k].first;ans.push_back(vp1[k].second);k++;} 
    if (A<0)ans.pop_back();
    
    return (ans);}
    if (vp3.size()==0 && vp4.size()==0){ 
    //subtask 2 / 7 points / N ≤ 3000; T[i] ≤ 2 for each i such that 0 ≤ i < N.
    //subtask 3 / 12 points /  T[i] ≤ 2 for each i such that 0 ≤ i < N. 
    
    //both of the subtasks have a common constraint T[i]<=2 hence we will use that to solve both the subtasks
    //Is there any point in 
    //  1: buying a T[i]==2 coupon after any T[i]==1. 
    //     because {X,Y|X is the P[i] where T[i]==1,Y is the P[i] where T[i]==2}
    //     ((A-X)*1-Y)*2<((A-Y)*2-X) where if we simplify it {0<X} hence no need.
    //     Inductively we can say that the structure should be something like (for the T values) 2,2,2,2,1,1,1,1,1
    //  2: for any structure if we seperate the 1s and 2s for the T values there can not be any {i,j|0<=i,j<=n-1,j=i+1}
    //     such that P[i]>=P[j] because ((A-P[i])*2-P[j])*2<((A-P[j])*2-P[i])*2 because if we simplify it we get
    //     P[j]<P[Pi] hence we must sort it.
    //  3: if at any point we have money>=2e14 we can just do anything we want since 2e14>=max(N)*max(P[i])
    //
    //With these two in mind for subtask 2 for every possible ending of the 2 chain
    //we use our subtask 1 solution to get the length of the max len of our ans if the 2 chain ended there 
    //hence our time complexity is o(vp2.size()*vp1.size())~o(n*n)=o(n^2)
    //
    //To get subtask 3 we just add Prefix sum followed by binary search to it.
    //hence our time complexity is o(vp2.size()*log(vp1.size()))~o(n*logn)
    
    vector <pair<long long,long long>> vp1;
    vector <pair<long long,long long>> vp2;
    vector <long long> psum1;
    vector <long long> psum2;
    long long sm1=0;
    long long sm2=A;
    
    vp1.push_back({0,-1});
    vp2.push_back({0,-1});
    
    
    for (long long i=0; i<P.size(); i++){
        if (T[i]==1){
        vp1.push_back({P[i],i});
    }}
    for (long long i=0; i<P.size(); i++){
        if (T[i]==2){
        vp2.push_back({P[i],i});
    }}
    
    sort(vp1.begin(),vp1.end());
    sort(vp2.begin(),vp2.end());
    
    for (long long i=0; i<vp1.size(); i++){
        sm1+=vp1[i].first;
        psum1.push_back(sm1);
    }
    
    for (long long i=0; i<vp2.size(); i++){
        sm2-=vp2[i].first;
        if (vp2[i].first==0){
        psum2.push_back(sm2);            
        }
        else if (sm2>=0){
        sm2=sm2*2;
        sm2=min(sm2,MX);
        psum2.push_back(sm2);
        }
        else{
        psum2.push_back(-1);
        }
    }
    vector <int> ans;

    long long k=0,maxh=0,maxpos=-1;
    
    for (long long i=0; i<vp2.size(); i++){
        if (psum2[i]>=0){
        long long kk=fnd(psum1,psum2[i]);
        if (kk+i>=maxh){maxpos=i;maxh=kk+i;}
    }}
    
    for (long long i=1; i<=maxpos; i++){
        ans.push_back(vp2[i].second);
    }
    for (long long i=1; i<=maxh-maxpos; i++){
        ans.push_back(vp1[i].second);        
    }
    return (ans);
}
}
/*
int main(){
    
    vector <int> v={4,5,6,7,1,2,3,4};
    vector <int> t={2,2,2,2,1,1,1,1};
  
    vector <int> aa;
  
    aa=max_coupons(10000000,v,t);
    
    for (int i=0; i<aa.size(); i++){
        cout<<aa[i]<<' ';
    }
    
}
*/



//

Compilation message (stderr)

festival.cpp: In function 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)':
festival.cpp:32:35: error: no matching function for call to 'std::vector<std::pair<long long int, long long int> >::push_back(__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&, int&)'
   32 |         if (T[i]==1){vp1.push_back(P[i],i)};
      |                      ~~~~~~~~~~~~~^~~~~~~~
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53,
                 from festival.cpp:1:
/usr/include/c++/13/bits/stl_vector.h:1281:7: note: candidate: 'constexpr void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<long long int, long long int>; _Alloc = std::allocator<std::pair<long long int, long long int> >; value_type = std::pair<long long int, long long int>]'
 1281 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1281:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/13/bits/stl_vector.h:1298:7: note: candidate: 'constexpr void std::vector<_Tp, _Alloc>::push_back(value_type&&) [with _Tp = std::pair<long long int, long long int>; _Alloc = std::allocator<std::pair<long long int, long long int> >; value_type = std::pair<long long int, long long int>]'
 1298 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1298:7: note:   candidate expects 1 argument, 2 provided
festival.cpp:33:35: error: no matching function for call to 'std::vector<std::pair<long long int, long long int> >::push_back(__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&, int&)'
   33 |         if (T[i]==2){vp2.push_back(P[i],i)};
      |                      ~~~~~~~~~~~~~^~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1281:7: note: candidate: 'constexpr void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<long long int, long long int>; _Alloc = std::allocator<std::pair<long long int, long long int> >; value_type = std::pair<long long int, long long int>]'
 1281 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1281:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/13/bits/stl_vector.h:1298:7: note: candidate: 'constexpr void std::vector<_Tp, _Alloc>::push_back(value_type&&) [with _Tp = std::pair<long long int, long long int>; _Alloc = std::allocator<std::pair<long long int, long long int> >; value_type = std::pair<long long int, long long int>]'
 1298 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1298:7: note:   candidate expects 1 argument, 2 provided
festival.cpp:34:35: error: no matching function for call to 'std::vector<std::pair<long long int, long long int> >::push_back(__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&, int&)'
   34 |         if (T[i]==3){vp3.push_back(P[i],i)};
      |                      ~~~~~~~~~~~~~^~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1281:7: note: candidate: 'constexpr void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<long long int, long long int>; _Alloc = std::allocator<std::pair<long long int, long long int> >; value_type = std::pair<long long int, long long int>]'
 1281 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1281:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/13/bits/stl_vector.h:1298:7: note: candidate: 'constexpr void std::vector<_Tp, _Alloc>::push_back(value_type&&) [with _Tp = std::pair<long long int, long long int>; _Alloc = std::allocator<std::pair<long long int, long long int> >; value_type = std::pair<long long int, long long int>]'
 1298 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1298:7: note:   candidate expects 1 argument, 2 provided
festival.cpp:35:35: error: no matching function for call to 'std::vector<std::pair<long long int, long long int> >::push_back(__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&, int&)'
   35 |         if (T[i]==4){vp4.push_back(P[i],i)};
      |                      ~~~~~~~~~~~~~^~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1281:7: note: candidate: 'constexpr void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<long long int, long long int>; _Alloc = std::allocator<std::pair<long long int, long long int> >; value_type = std::pair<long long int, long long int>]'
 1281 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1281:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/13/bits/stl_vector.h:1298:7: note: candidate: 'constexpr void std::vector<_Tp, _Alloc>::push_back(value_type&&) [with _Tp = std::pair<long long int, long long int>; _Alloc = std::allocator<std::pair<long long int, long long int> >; value_type = std::pair<long long int, long long int>]'
 1298 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1298:7: note:   candidate expects 1 argument, 2 provided
festival.cpp:43:38: error: 'vp' was not declared in this scope; did you mean 'vp4'?
   43 |     while (A>=0 && k<vp1.size()){A=A-vp[k].first;ans.push_back(vp1[k].second);k++;}
      |                                      ^~
      |                                      vp4
festival.cpp:129:1: warning: control reaches end of non-void function [-Wreturn-type]
  129 | }
      | ^