Submission #1286776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286776		kawhiet	Festival (IOI25_festival)	C++20	5 / 100	40 ms	7128 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();
    while (l + 1 < r) {
      int m = (l + r) / 2;
      if (pre[m] <= k) {
        l = m;
      } else {
        r = m;
      }
    }
    vector<int> ret;
    for (int i = 0; i < l; i++) {
      ret.push_back(b[i][1]);
    }
    return ret;
  };
  vector<int> res = get(x), cur;
  int mx = res.size();
  for (int i = 0; i < a.size(); i++) {
    cur.push_back(a[i][1]);
    x = (x - a[i][0]) * 2;
    if (x < 0) {
      break;
    }
    x = min(x, inf);
    auto s = get(x);
    if (s.size() + cur.size() > mx) {
      vector<int> new_res = cur;
      new_res.insert(new_res.end(), s.begin(), s.end());
      swap(res, new_res);
      mx = res.size();
    }
  }
  return res;
}

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