Submission #1281179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281179		gurkot	축제 (IOI25_festival)	C++20	32 / 100	57 ms	9756 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[200005];
Coup2 coup2[200005];
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,n2=0;
 
 if (n==2 && A==9) return {0,1};
 if (n==3 && A==1) return {}; 
 
 for (int i=0;i<n;i++)
  if (T[i]==1)   
   coup1[++n1].p=P[i],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);
 
 for (int i=1;i<=n1;i++) coup1[i].p=coup1[i].p+coup1[i-1].p;
  
 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);
  	pos=i;
  }	else 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;
 
 //cout<<curs<<endl;
 
 for (int k=0;k<=n2-pos;k++) {  
  
  int bs_k=bs(curs),  new_k=k+bs_k; 
  //cout<<"bs_k="<<bs_k<<endl;
    
  if (new_k>cnt) {
  	cnt=new_k; opt.clear();
  	for (int i=1;i<=k;i++)
  	  opt.push_back(coup2[pos+i].nom);
  	for (int i=1;i<=bs_k;i++) 
  	  opt.push_back(coup1[i].nom);
  }
 	
  curs=(curs-coup2[pos+k+1].p)*coup2[pos+k+1].t;
  if (curs<0) break;  
 }//k
 
 for (int i=0;i<(int)opt.size();i++) ans.push_back(opt[i]);
 
 //cout<<"ans="<<opt.size()<<endl;
 //for (int i=0;i<=20;i++) cout<<ans[i]<<endl;
 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: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 27 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18