Submission #1252897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252897		flashmt	Festival (IOI25_festival)	C++20	24 / 100	57 ms	8244 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const long long oo = 1LL << 60;

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
  vector<pair<int, int>> a[4];
  int n = size(P);
  for (int i = 0; i < n; i++)
    a[T[i] - 1].push_back({P[i], i});

  for (int i = 0; i < 4; i++)
    sort(begin(a[i]), end(a[i]));

  vector<long long> sum1 = {0};
  for (auto [x, _] : a[0])
    sum1.push_back(sum1.back() + x);

  vector<int> cur(4), fixed;
  long long has = A;
  while (1)
  {
    int found = 0;
    for (int t = 1; t < 4; t++)
      if (cur[t] < size(a[t]))
      {
        auto [p, id] = a[t][cur[t]];
        long long after = min((has - p) * (t + 1), oo);
        if (after >= has)
        {
          has = after;
          cur[t]++;
          fixed.push_back(id);
          found = 1;
          break;
        }
      }

    if (!found)
      break;
  }

  auto comp = [&](int u, int v)
  {
    long long costUV = 1LL * P[u] * T[u] * T[v] + 1LL * P[v] * T[v];
    long long costVU = 1LL * P[v] * T[v] * T[u] + 1LL * P[u] * T[u];
    return costUV < costVU;
  };

  auto get1 = [&](long long has)
  {
    return upper_bound(begin(sum1), end(sum1), has) - begin(sum1) - 1;
  };

  vector<int> ans = {0, int(size(fixed)), -1};
  auto updateAns = [&](long long has, int extra = -1)
  {
    int cnt0 = get1(has);
    int totalCur = cnt0 + int(size(fixed)) + (extra >= 0);
    int totalAns = ans[0] + ans[1] + (ans[2] >= 0);
    if (totalCur > totalAns)
      ans = {cnt0, int(size(fixed)), extra};
  };

  while (1)
  {
    updateAns(has);
    int bestT = -1, bestId = -1;
    for (int t = 1; t < 4; t++)
      if (cur[t] < size(a[t]))
      {
        auto [p, id] = a[t][cur[t]];
        long long after = (has - p) * (t + 1);
        if (after < 0)
          continue;

        updateAns(after, id);

        if (bestId < 0 || comp(id, bestId))
        {
          bestT = t;
          bestId = id;
        }
      }

    if (bestT < 0)
      break;

    has = (has - P[bestId]) * (T[bestId]);
    fixed.push_back(a[bestT][cur[bestT]++].second);
  }

  vector<int> coupons;
  for (int i = 0; i < ans[1]; i++)
    coupons.push_back(fixed[i]);
  if (ans[2] >= 0)
    coupons.push_back(ans[2]);
  for (int i = 0; i < ans[0]; i++)
    coupons.push_back(a[0][i].second);
  return coupons;
}

• 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