Submission #1257068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257068		ogkostya	Festival (IOI25_festival)	C++20	5 / 100	41 ms	7608 KiB

festival

#include "festival.h"
#include <algorithm>
#include <climits>

long long Mult(long long a, int t)
{
  if (LLONG_MAX / t < a)
    return LLONG_MAX;
  return a * t;
}

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T)
{
  int n = P.size();
  long long a = A;
  std::vector<std::pair<long long, int>> x[4];
  for (int i = 0; i < 4; i++)
    x[i] = std::vector<std::pair<long long, int>>();
  for (int i = 0; i < n; i++)
  {
    x[T[i] - 1].push_back(std::make_pair(1LL * P[i], i));
  }
  for (int i = 0; i < 4; i++)
  {
    std::sort(x[i].begin(), x[i].end());
  }

  std::vector<int> ans = {};

  int j = 0;
  while (j < x[1].size() && x[1][j].first * 2 <= a)
  {
    ans.push_back(x[1][j].second);
    a -= x[1][j].first;
    a = Mult(a, 2);
    j++;
  }

  for (int i = 1; i < x[0].size(); i++)
    x[0][i].first += x[0][i - 1].first;

  int max = 0, mj = -1, mi = -1;
  {
    int l = -1, r = x[0].size();
    while (l + 1 < r)
    {
      int m = (l + r) >> 1;
      if (x[0][m].first <= a)
        l = m;
      else
        r = m;
    }
    max = l + 1;
    mj = j - 1;
    mi = l;
  }
  int jj = j;
  for (; j < x[1].size(); j++)
  {
    if (x[1][j].first <= a)
    {
      a -= x[1][j].first;
      int l = -1, r = x[0].size();
      while (l + 1 < r)
      {
        int m = (l + r) >> 1;
        if (x[0][m].first <= a)
          l = m;
        else
          r = m;
      }

      if (j - jj + l + 1 > max)
      {
        max = j - jj + l + 1;
        mj = j;
        mi = l;
      }
    }
    else
    {
      break;
    }
  }

  for (int i = jj; i <= mj; i++)
  {
    ans.push_back(x[1][i].second);
  }
  for (int i = 0; i <= mi; i++)
  {
    ans.push_back(x[0][i].second);
  }

  return ans;
}

• 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