Submission #1253515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253515		bynix	Festival (IOI25_festival)	C++20	24 / 100	61 ms	12728 KiB

festival

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

typedef long long ll;

const ll lim = 1e18;

vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
  vector<int> R;

  ll N = P.size();
  
  vector<pair<ll, ll>> t1, t2;
  vector<ll> pre1(N+1, lim*2), pre2(N+1, -1);

  for (ll i = 0; i < N; i++){
    if (T[i] == 1) t1.push_back({P[i], i});
    else t2.push_back({P[i], i});
  }

  ll t1s = t1.size(), t2s = t2.size();
  sort(t1.begin(), t1.end());
  sort(t2.begin(), t2.end());
  
  pre1[0] = 0;
  for (ll i = 0; i < t1s; i++)
    pre1[i + 1] = pre1[i] + t1[i].first, pre1[i + 1] = min(pre1[i + 1], lim);

  pre2[0] = A;
  for (ll i = 0; i < t2s; i++){
    pre2[i + 1] = (pre2[i] - t2[i].first) * 2, pre2[i + 1] = min(pre2[i + 1], lim);
    if (pre2[i] < 0) break; 
  }

  ll mc = 0ll, mt1 = 0ll, mt2 = 0ll, ct1 = 0ll;
  for (ll i = 0; i <= t2s; i++){
    ll a = pre2[i];
    if (a < 0) break;

    ll pos = upper_bound(pre1.begin(), pre1.end(), a) - pre1.begin();
    if (pos == 0) ct1 = 0;
    else ct1 = min(pos - 1, t1s);

    if (ct1 + i > mc) mc = ct1 + i, mt1 = ct1, mt2 = i;
  }

  for (ll i = 0; i < mt2; i++) R.push_back(t2[i].second);
  for (ll i = 0; i < mt1; i++) R.push_back(t1[i].second);
  return R;
}

• 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