Submission #1251290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251290		mychecksedad	Festival (IOI25_festival)	C++20	27 / 100	74 ms	9900 KiB

festival

#include "festival.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define ll long long int
const int N = 2e5+100;


void apply(ll &C, ll p, ll t){
  if((C-p) > 1e17){
    return;
  }
  C = (C-p)*t;
}

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
  int n = (int) P.size();
  vector<array<ll, 3>> B;
  for(int i = 0; i < n; ++i){
    B.pb({P[i], T[i], i});
  }
  function<int(ll, ll ,ll)> F = [&](ll p, ll t, ll C){
    return (t)*C - p*t;
  };
  vi RES;
  ll CC = A;
  while(B.size()){
    if(CC > 1e17){
      for(auto x: B){
        RES.pb(x[2]);
      }
      break;
    }
    sort(all(B), [&](const array<ll, 3> &x, const array<ll, 3> &y){
      if(x[1] == 1) return false;
      if(y[1] == 1) return true;
      // bool take1 = (CC-x[0])*x[1] >= y[0];
      // bool take2 = (CC-y[0])*y[1] >= x[0];
      // if(take1 && take2){
        // ll c = ((CC-x[0])*x[1] - y[0]) * y[1];
        // ll d = ((CC-y[0])*y[1] - x[0]) * x[1];
        double c = x[0]*x[1] / (double)(y[0]*y[1]);
        double d = (x[1]-1) / (double)(y[1]-1);
        return c<d;
      // }
      assert(false);
      // if(take1) return true;
      // if(take2) return false;
      return F(x[0], x[1], CC) > F(y[0], y[1], CC);
    });
    // for(auto [x, y, z]: B) cerr << x << ' ' << y << ' ' << z << '\n';
    for(int j = 0; j < n; ++j){
      
        RES.pb(B[j][2]);
      
    }
    break;
    cerr << '\n';
    cerr << '\n';
  }
  return RES;


  vector<pair<ll, int>> X, Y;
  vector<ll> pref;
  ll C = A;
  for(int i = 0; i < n; ++i){
    if(T[i] == 1){
      X.pb({P[i], i});
    }else{
      Y.pb({P[i], i});
    }
  }
  sort(all(X));
  sort(all(Y));
  pref.resize(X.size()+1);
  pref[0] = 0;
  for(int i = 1; i <= X.size(); ++i) pref[i] = pref[i - 1] + X[i - 1].ff;

  function<int(ll)> get = [&](ll sum){
    return lower_bound(all(pref), sum) - pref.begin();
  };
  int best = 0, cnt = get(C);
  for(int i = 0; i < Y.size(); ++i){
    if(C < Y[i].ff){
      break;
    }
    apply(C, Y[i].ff, 2);
    int num = i + 1 + get(C);
    if(num > cnt){
      cnt = num;
      best = i + 1;
    }
  }
  vi res;
  C = A;
  for(int j = 0; j < best; ++j){
    res.pb(Y[j].ss);
    apply(C, Y[j].ff, 2);
  }
  for(int j = 0; j < X.size(); ++j){
    if(X[j].ff <= C){
      C -= X[j].ff;
      res.pb(X[j].ss);
    }
  }

  return res;
}

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