제출 #1257177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257177		ogkostya	Festival (IOI25_festival)	C++20	32 / 100	58 ms	8468 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 - 1;
  return a * t;
}

long long Step2(std::vector<std::pair<long long, int>> &P, int &j, long long a, int c, int x)
{
  if (j < P.size() && c * P[j].first <= a * (c - 1))
  {
    return x * P[j].first;
  }
  return LLONG_MAX;
}

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 ind[] = {0, 0, 0, 0};
  while (true)
  {
    long long val[] = {LLONG_MAX, Step2(x[1], ind[1], a, 2, 12), Step2(x[2], ind[2], a, 3, 9), Step2(x[3], ind[3], a, 4, 8)};
    int min = 1;
    for (int j = 2; j < 4; j++)
    {
      if (val[j] < val[min])
        min = j;
    }
    if (val[min] == LLONG_MAX)
      break;

    ans.push_back(x[min][ind[min]].second);
    a = (a - x[min][ind[min]].first) * (min + 1);
    ind[min]++;
  }

  if (x[2].size() > 0 || x[3].size() > 0)
  {
    for (int j = 3; j >= 0; j--)
    {
      for (int i = ind[j]; i < x[j].size(); i++)
      {
        if (x[j][i].first <= a)
        {
          ans.push_back(x[j][i].second);
          a = Mult(a - x[j][i].first, j + 1);
        }
      }
    }
  }
  else
  {
    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 = ind[1] - 1;
      mi = l;
    }

    for (int j = ind[1]; j < x[1].size(); j++)
    {
      if (x[1][j].first <= a)
      {
        a -= x[1][j].first;
        a = Mult(a, 2);
        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 - ind[1] + l + 2 > max)
        {
          max = j - ind[1] + l + 2;
          mj = j;
          mi = l;
        }
      }
      else
      {
        break;
      }
    }

    for (int i = ind[1]; 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: 27 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18