Submission #1252485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252485		Jakub_Wozniak	Festival (IOI25_festival)	C++20	24 / 100	60 ms	10164 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200009;
#define st first
#define nd second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
vector <pll> t[5];
vector<ll> pref;
vector <ll> HA;

int bs(int A)
{
  int l = 0 , r = pref.size() , sro;
  while(r - l > 1)
  {
    sro = (l+r)/2;
    if(pref[sro] <= A)l=sro;
    else r = sro;
  }
  return l;
}

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) 
{
  ll rA = A;
  int N = P.size();
  for(int i = 0; i < N ; i++)
  {
    t[T[i]].push_back({P[i],i});
  }
  for(int j = 1 ; j <= 4 ; j++)sort(t[j].begin() , t[j].end());
  pref.push_back(0);
  for(auto p : t[1])pref.push_back(pref[pref.size()-1] + p.st);

  vector <int> K;
  HA.push_back(rA);
  int ile = bs(rA) , ind = 0;
  
  for(int i = 1;  i <= t[2].size() ; i++)
  {
    if(rA < t[2][i-1].st)break;
    int akt = i;
    rA -= t[2][i-1].st;
    rA *= 2;
    HA.push_back(rA);
    akt += bs(rA);


    if(rA >= (1e+17))
    {
      vector <int> temp;
      for(auto p : t[2])temp.push_back(p.nd);
      for(auto p : t[1])temp.push_back(p.nd);
      return temp;
    }

    if(akt > ile)
    {
      ile = akt;
      ind = i;
    }
  }

  for(int i = 0 ; i < ind;  i++)K.push_back(t[2][i].nd);
  int I = bs(HA[ind]);
  for(int i = 0 ; i < I ; i++)K.push_back(t[1][i].nd);

  return {K};
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18