제출 #1257398

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

long long Step1(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 a - (a - P[j].first) * c;
  }
  return LLONG_MAX;
}

std::vector<std::pair<long long, int>> x[4];
int ind[4];
int kef[4] = {1, 12, 9, 8};
int lim[4] = {1, 32, 20, 16};
std::vector<int> maxans;
int ans[200005];
std::pair<long long, int> Q[200005];

std::vector<int> PP;
std::vector<int> TT;

void Dfs(int j, long long a, int index, int count)
{
  if (j == 0)
  {
    std::vector<std::pair<long long, int>> W;
    for (int i = 0; i < count; i++)
    {
      W.push_back(Q[i]);
    }
    std::sort(W.begin(), W.end());

    for (const std::pair<long long, int> &w : W)
    {
      if (PP[w.second] > a)
        return;
      a = (a - PP[w.second]) * TT[w.second];
    }

    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 + count + l + 1)
    {
      maxans = std::vector<int>();
      for (int i = 0; i < index; i++)
      {
        maxans.push_back(ans[i]);
      }
      for (const std::pair<long long, int> &w : W)
      {
        maxans.push_back(w.second);
      }
      for (int i = 0; i <= l; i++)
      {
        maxans.push_back(x[0][i].second);
      }
    }
    return;
  }
  Dfs(j - 1, a, index, count);
  for (int i = ind[j], k = 0; k < lim[j] && i < x[j].size(); i++, k++)
  {
    Q[count + k] = std::make_pair(1LL * x[j][i].first * kef[j], x[j][i].second);
    Dfs(j - 1, a, index, count + k + 1);
  }
}

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T)
{
  PP = P;
  TT = 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, kef[1]), Step2(x[2], ind[2], a, 3, kef[2]), Step2(x[3], ind[3], a, 4, kef[3])};
    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(3, a, ans_i, 0);
  }
  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: 15 / 15
• Subtask 5: 27 / 27
• Subtask 6: 16 / 16
• Subtask 7: 18 / 18