제출 #1257261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257261		ogkostya	Festival (IOI25_festival)	C++20	51 / 100	60 ms	9400 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;
}

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

std::vector<std::pair<long long, int>> x[4];
int ind[4];
std::vector<int> maxans;
int ans[200005];

void Dfs(int j, long long a, int index)
{
  if (j == 0)
  {
    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 (maxans.size() < index + l + 1)
    {
      maxans = std::vector<int>();
      for (int i = 0; i < index; i++)
      {
        maxans.push_back(ans[i]);
      }
      for (int i = 0; i <= l; i++)
      {
        maxans.push_back(x[0][i].second);
      }
    }
    return;
  }
  Dfs(j - 1, a, index);
  for (int i = ind[j]; i < x[j].size(); i++)
  {
    if (x[j][i].first <= a)
    {
      a = (a - x[j][i].first) * (j + 1);
      ans[index++] = x[j][i].second;
      Dfs(j - 1, a, index);
    }
    else
      break;
  }
}

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T)
{
  int n = P.size();
  long long a = A;
  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());
  }

  int ans_i = 0;

  std::fill(ind, ind + 4, 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[ans_i++] = x[min][ind[min]].second;
    a = Mult(a - x[min][ind[min]].first, min + 1);
    ind[min]++;
  }

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

  if (x[2].size() > 0 || x[3].size() > 0)
  {
    Dfs(0, a, ans_i);
    while (true)
    {
      long long val[] = {LLONG_MAX, Step3(x[1], ind[1], a, 2, 12), Step3(x[2], ind[2], a, 3, 9), Step3(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[ans_i++] = x[min][ind[min]].second;
      a = Mult(a - x[min][ind[min]].first, min + 1);
      ind[min]++;

      Dfs(0, a, ans_i);
    }
  }
  else
  {
    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;
      }
    }
    maxans = std::vector<int>();
    for (int i = 0; i < ans_i; i++)
    {
      maxans.push_back(ans[i]);
    }

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

  return maxans;
}

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