Submission #1312510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312510		Dedibeat	Festival (IOI25_festival)	C++20	5 / 100	38 ms	7128 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(v) (v).begin(), (v).end()
const int LIM = 1e18;
ll safe_mul(ll x, ll y)
{
  if(x * y >= LIM) return LIM;
  return x * y;
}
std::vector<int> max_coupons(int aa, std::vector<int> P, std::vector<int> T) {
  ll A = aa;
  int n = T.size();
  vector<int> one, two;
  for(int i = 0; i < n; i++)
  {
    if(T[i] == 1) one.push_back(i);
    else two.push_back(i);
  }
  sort(all(one), [&](int i, int j)
  {
    return P[i] < P[j];
  });
  sort(all(two), [&](int i, int j)
  {
    return P[i] < P[j];
  });


  vector<ll> pref((int)one.size());
  ll sum = 0;
  for(int i = 0; i < one.size(); i++) 
  {
    sum += P[one[i]];
    pref[i] = sum;
  }

  auto go = [&](int tok)
  {
    int ans = 0;
    for(int i : one) 
    {
      ans++;
      if(tok < P[i]) break;
      tok -= P[i];
    }
    return ans;
  };

  int x = lower_bound(all(pref), A + 1) - pref.begin();
  int y = 0;
  int mx = x;
  for(int i = 0; i < two.size(); i++)
  {
    if(A < P[two[i]]) break;
    A = safe_mul(A - P[two[i]], 2);
    int j = lower_bound(all(pref), A + 1) - pref.begin();
    int tot = (i + 1 + j);
    if(tot > mx) 
    {
      x = j;
      y = i + 1;
      mx = x + y;
    }
  }

  vector<int> ans;
  for(int i = 0; i < y; i++) ans.push_back(two[i]);
  for(int i = 0; i < x; i++) ans.push_back(one[i]);
  return ans;
}

Compilation message (stderr)

festival.cpp:6:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    6 | const int LIM = 1e18;
      |                 ^~~~

• 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