Submission #1286165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286165		eri16	Festival (IOI25_festival)	C++20	51 / 100	77 ms	11052 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);}
    else 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});

    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{
        
    //subtask 5 / 27 points / Nayra can buy all N coupons (in some order).
    //since there is a sequence where we can acquire every coupon we just have to find
    //a sequence that lets us have all of them hence we will no longer have to deal with some money issues
    //doing simple algebra gives the formula that if we pick (i,j) over (j,i) then 
    //P[i]*T[i]/(T[i]-1)<P[j]*T[j]/(T[j]-1) 
    long long a = A;
    vector<int> vv(P.size());
    for (int i=0; i<P.size(); i++)vv[i]=i;

    sort(vv.begin(), vv.end(), [&](int i, int j) {
        if (T[i]==T[j]) return P[i]<P[j];
        return 1ll*P[i]*T[i]*(T[j]-1)<1ll*P[j]*T[j]*(T[i]-1);
    });
    
    vector<int> ans;
    for(int i=0; i<P.size(); i++){
        if(a>=P[vv[i]]){
            a=(a-P[vv[i]])*T[vv[i]];
            a=min(a,MX);
            ans.push_back(vv[i]);
        }
    }
    return ans;}

}

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