Submission #1258477

#TimeUsernameProblemLanguageResultExecution timeMemory
1258477medmdgFestival (IOI25_festival)C++20
5 / 100
84 ms22700 KiB
#include "festival.h" #include<bits/stdc++.h> #define mk(a,b) make_pair(a,b) #define pb(a) push_back(a) using namespace std; typedef long long ll; ll n; vector<pair<ll,int>> t[4]; set<pair<ll,ll>> s; ll a; vector<ll> p; const ll M=1e15; int getP1(ll a){ if(a<0)return 0; set<pair<ll,ll>>::iterator t=s.lower_bound(mk(a+1,-1)); if(t==s.begin())return 0; t--; ll ans= (*t).second; return ans; } vector<int> sub3(){ ll ma=getP1(a); ll nb=0; for(int i=0;i<t[1].size();i++){ a-=t[1][i].first; if(a<1e17) a*=2; if(a<0)break; ll nma=getP1(a)+i+1; if(nma>ma){ ma=nma; nb=i+1; } } vector<int> ans; for(int i=0;i<nb;i++){ ans.push_back(t[1][i].second); } for(int i=nb;i<ma;i++){ ans.push_back(t[0][i-nb].second); } return ans; } ll pick_best(ll a,ll v1,ll v2,ll v3){ a=min(a,M); ll xa=a-2*v1,xb=2*a-3*v2,xc=3*a-4*v3; if(v1==-1){ if(v2==-1)return 2; if(v3==-1)return 1; if(3*xb>=2*xc)return 1; return 2; }else if(v2==-1){ if(v3==-1)return 0; if( 3*xa>=xc)return 0; return 2; } else{ if(v3==-1){ if(2*xa>=xb) return 0; return 1; } } if(2*xa>=xb){ if( 3*xa>=xc)return 0; return 2; } if(3*xb>=2*xc)return 1; return 2; } pair<vector<int>,int> sub5(int maTurns){ ll ta=a; vector<int> ans; ll i=0,j=0,k=0; while(i+j+k<maTurns && (i<t[1].size()||j<t[2].size()||k<t[3].size())){ ll v1=-1,v2=-1,v3=-1; if(i<t[1].size()) v1=t[1][i].first; if(j<t[2].size()) v2=t[2][j].first; if(k<t[3].size()) v3=t[3][k].first; ll v=pick_best(ta,v1,v2,v3); if(v==0)ans.pb(t[1][i++].second); if(v==1)ans.pb(t[2][j++].second); if(v==2)ans.pb(t[3][k++].second); if(ta-p[ans.back()]<0){ ans.pop_back(); break; } ta-=p[ans.back()]; if(ta<M) ta*=(v+2); } int c2=getP1(ta); return mk(ans,c2); } vector<int> sub6(){ int val=getP1(a); vector<int> ans; for(int i=1;i<=60;i++){ pair<vector<int>,int> t=sub5(i); if(t.first.size()+t.second>val){ val=t.first.size()+t.second; ans=t.first; } } int v=ans.size(); for(int i=v;i<val;i++){ ans.push_back(t[0][i-v].second); } return ans; } vector<int> max_coupons(int A, vector<int> P, vector<int> T) { for(int i=0;i<4;i++)t[i].clear(); for(int i=0;i<T.size();i++){ t[T[i]-1].push_back(mk(P[i],i)); } for(int i=0;i<4;i++) sort(t[i].begin(),t[i].end()); s.clear(); s.insert(mk(0,0)); ll ps=0; for(int i=0;i<t[0].size();i++){ ps+=t[0][i].first;s.insert(mk(ps,i+1));} n=P.size(); a=A; p.clear(); for(auto x:P)p.push_back(x); return sub6(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...