| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1286162 | eri16 | Festival (IOI25_festival) | C++20 | 0 ms | 0 KiB |
#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(long long 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 will no longer have to deal with some money issues and negative money when doing the best money maximizing algorythm
//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)
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;}
}