| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1326216 | somefolk | Festival (IOI25_festival) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
std::vector<signed> max_coupons(signed A, std::vector<signed> P,
std::vector<signed> T){
int n=P.size();
pair<int,int> t1[n],t2[n];
int k1=-1,k2=-1;
for(int i=0; i<n; i++){
if(T[i]==2){
t2[++k2].f=P[i];
t2[k2].s=i;}
else{
t1[++k1].f=P[i];
t1[k1].s=i;}
}
k1++; k2++;
sort(t1, t1+k1);
sort(t2, t2+k2);
for(int i=1; i<k1; i++) t1[i].f+=t1[i-1].f;
int c=A;
int m1=0,m2=0;
int z=1e16;
for(int i=0; i<=k2&&c>-1; i++){
int l=0, r=k1-1;
int x = -1;
while(l<=r){
int m=l+(r-l)/2;
if(t1[x].f<=c)
x = m;
l=m+1;
else
r=m-1;
}
if((m1+m2)<i+x+1){
m1=x+1;
m2=i;
}
c=min((c-t2[i].f)*2,z);
}
vector<signed> R;
for( int i=0; i<m2; i++)
R.push_back(t2[i].s);
for(int i=0; i<m1; i++)
R.push_back(t1[i].s);
return R;
}
