Submission #1281117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281117		gurkot	Festival (IOI25_festival)	C++20	0 / 100	41 ms	7736 KiB

festival

#include "festival.h"
#include <iostream>
#include <algorithm>
using namespace std;

const long long smax=1e15;

struct Coup2{long long p; int t,nom;};
bool operator <(Coup2 a,Coup2 b){
 return ((a.p*a.t+b.p)*b.t<(b.p*b.t+a.p)*a.t);
}

struct Coup1{long long p; int nom;};
bool operator <(Coup1 a,Coup1 b){
 return a.p<b.p;
}

Coup1 coup1[200001];
Coup2 coup2[200001];
int n,n1,n2;

int bs(long long s){
 int A=0,B=n1;
 while (A<B){
  int C=(A+B+1)/2;
  if (coup1[C].p<=s) A=C;
                else B=C-1;	
 }
 return A;
}


vector<int> max_coupons(int A, vector<int> P, 
                               vector<int> T) {
 n=(int) P.size(),n1=0;
 for (int i=0;i<n;i++)
  if (T[i]==1){
   n1++;
   coup1[n1].p=P[i]+coup1[n1-1].p;
   coup1[n1].nom=i;
  }
  else
   coup2[++n2].p=P[i],coup2[n2].t=T[i],coup2[n2].nom=i;

 sort(coup1+1,coup1+n1+1); 
 sort(coup2+1,coup2+n2+1);
 
 //cout<<"n1,n2="<<n1<<" "<<n2<<endl;
 
 
 long long s=A; int pos=0;
 vector <int> ans={};
 for (int i=1;i<=n2;i++) {
  long long curs=(s-coup2[i].p)*coup2[i].t;
  if (curs>=s) {
  	s=curs;
  	ans.push_back(coup2[i].nom);
  }	else {
  	pos=i;break;
  }  	
 }//i
 
 /*
 cout<<"***coup2:"<<endl;
 for (int i=1;i<=n2;i++) cout<<coup2[i].nom<<endl;
 cout<<"pos="<<pos<<endl;
 cout<<"vec ans: ";
 for (int i=0;i<ans.size();i++) cout<<" "<<ans[i];
 cout<<endl;
 */
 
 vector <int> opt;
 int cnt=0;
 long long curs=s;
 //cout<<"before bs, s="<<s<<endl;
 
 for (int k=0;k<=n2-pos+1;k++) {
  if (curs<0) break;
  int bs_k=bs(curs),new_k=bs_k+k; 
   
  if (new_k>cnt) {
  	cnt=new_k; opt.clear();
  	for (int i=1;i<=k;i++)
  	  opt.push_back(coup2[pos+i-1].nom);
  	for (int i=1;i<=bs_k;i++) 
  	  opt.push_back(coup1[i].nom);
  }	
  curs=(curs-coup2[pos+k].p)*coup2[pos+k].t;
  
 }//k
 for (int x:opt) ans.push_back(x);
 return ans;
}

/*

4 13
4 1
500 3
8 3
14 4
out:
3
2 3 0


2 9
6 2
5 3

out:
2
0 1



*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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