Submission #1286145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286145		eri16	Festival (IOI25_festival)	C++20	5 / 100	39 ms	9092 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-vp1[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 <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);}
    
    else{return P;}

}
/*
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]<<' ';
    }
    
}*/




//

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18