Submission #1286080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286080		eri16	Festival (IOI25_festival)	C++20	5 / 100	45 ms	7976 KiB

festival

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

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

    while (l<r) {
        int 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<int,int>> vp1;
    vector <pair<int,int>> 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 (int i=0; i<P.size(); i++){
        if (T[i]==1){
        vp1.push_back({P[i],i});
    }}
    for (int 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 (int i=0; i<vp1.size(); i++){
        sm1+=vp1[i].first;
        psum1.push_back(sm1);
    }
    
    for (int 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;
        psum2.push_back(sm2);
        }
        else{
        psum2.push_back(-1);
        }
    }
    
    
    vector <int> ans;
    
    int k=0,maxh=0,maxpos=-1;
    
    for (int i=0; i<vp2.size(); i++){
        if (psum2[i]>=0){
        int kk=fnd(psum1,psum2[i]);
        if (kk+i>=maxh){maxpos=i;maxh=kk+i;}
    }}
    
    for (int i=1; i<=maxpos; i++){
        ans.push_back(vp2[i].second);
    }
    for (int i=1; i<=maxh-maxpos; i++){
        ans.push_back(vp1[i].second);        
    }
    /*
    for (int i=0; i<psum1.size(); i++){
        cout<<psum1[i]<<' ';
    }    
    cout<<"\n";
    for (int i=0; i<psum2.size(); i++){
        cout<<psum2[i]<<' ';
    }    
    cout<<"\n";    
    */



    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(7,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