Submission #1265869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265869		thenpc	Festival (IOI25_festival)	C++20	5 / 100	42 ms	8636 KiB

festival

#include <bits/stdc++.h>
#include "festival.h"
using namespace std;
#define ll long long
vector<int> max_coupons(int a,vector<int> p,vector<int> t){
  vector<pair<int,int>> v[5];
  vector<int> u;
  ll sum2[200005],sum[200005];
  for(int i=0;i<p.size();i++){
    v[t[i]].push_back({p[i],i});
  }
  int cnt=v[2].size()+1;
  sort(v[1].begin(),v[1].end());
  sort(v[2].begin(),v[2].end());
  for(int i=0;i<v[2].size();i++){
    if(a<(a-v[2][i].first)*2){
      a=(a-v[2][i].first)*2;
      u.push_back(v[2][i].second);
    }
    else{
      cnt=i;
      break;
    }
  }
  if (cnt <= v[2].size()) {
        v[2].erase(v[2].begin(), v[2].begin() + cnt);
    } else {
        v[2].clear(); 
    }
  int cnt1=0,cnt2=0;
  if(v[2].size()>0){
    sum2[0]=v[2][0].first;
  }
  for(int i=1;i<v[2].size();i++){
    sum2[i]=sum2[i-1]+v[2][i].first/pow(2,i);
    
  }
  int pos=-1;
  int ma=0;
  for(int i=0;i<v[1].size();i++){
    if(i>0){
      sum[i]=sum[i-1]+v[1][i].first;
    }
    else{
      sum[i]=v[1][i].first;
    }
    ll x=a-sum[i];
    if(x<0){
      break;
    }
    ll *it = upper_bound(sum2,sum2+v[2].size(), x);
    ll idx=it-sum2;
    if(ma<i+1+idx){
      ma=i+1+idx;
      pos=i;
    }
  }
  for(int i=0;i<ma-pos-1;i++){
    u.push_back(v[2][i].second);
  }
  for(int i=0;i<=pos;i++){
    u.push_back(v[1][i].second);
  }
  return u;
}

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