Submission #1286779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286779		kawhiet	Festival (IOI25_festival)	C++20	24 / 100	55 ms	9648 KiB

festival

#include <bits/stdc++.h>
#include "festival.h"
using namespace std;

constexpr int64_t inf = 1e15;

vector<int> max_coupons(int A, vector<int> p, vector<int> t) {
  int n = p.size();
  vector<array<int, 2>> a, b;
  for (int i = 0; i < n; i++) {
    if (t[i] == 2) {
      a.push_back({p[i], i});
    } else {
      b.push_back({p[i], i});
    }
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  int m = b.size();
  vector<int64_t> pre(m + 1);
  for (int i = 0; i < m; i++) {
    pre[i + 1] = pre[i] + b[i][0];
  }
  int64_t x = A;
  auto get = [&](int64_t k) {
    int l = 0, r = b.size() + 1;
    while (l + 1 < r) {
      int m = (l + r) / 2;
      if (pre[m] <= k) {
        l = m;
      } else {
        r = m;
      }
    }
    return l;
  };
  int l = 0, r = get(x);
  int mx = r;
  for (int i = 0; i < a.size(); i++) {
    x = (x - a[i][0]) * 2;
    if (x < 0) {
      break;
    }
    x = min(x, inf);
    int j = get(x);
    if (i + j + 1 > mx) {
      mx = i + j + 1;
      l = i + 1;
      r = j;
    }
  }
  vector<int> res;
  for (int i = 0; i < l; i++) {
    res.push_back(a[i][1]);
  }
  for (int i = 0; i < r; i++) {
    res.push_back(b[i][1]);
  }
  return res;
}

• 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