#include "festival.h" #include <bits/stdc++.h> #define all(V) V.begin(), V.end() #define rall(V) V.rbegin(), V.rend() using namespace std; #define ll long long struct cp { ll p, id; bool operator<(const cp &o) const { return p < o.p; } }; bool cmp(cp a, cp b) { return a.p < b.p; } vector<deque<cp>> V; int N; ll X; ll stop = -1; vector<int> ord; ll ansmax = 0; ll t = 0; ll scegli1 = 0; vector<ll> p1; vector<ll> cesti1; std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) { V = vector(5, deque<cp>()); N = P.size(); X = A; for(int i=0; i<N; i++) { V[T[i]].push_back({P[i], i}); } for(int i=1; i<5; i++) sort(all(V[i])); ll p = 0; for(int i=0; i<V[1].size(); i++) { p += V[1][i].p; p1.push_back(p); cesti1.push_back(V[1][i].id); } cp search = {X, -1}; ansmax = scegli1 = lower_bound(all(p1), X) - p1.begin(); while(1) { fprintf(stderr, "==============\nansmax=%d, t=%d, scegli1=%d\n", ansmax, t, scegli1); ll a, b, c; a = b = c = stop; if(!V[2].empty()) a = V[2].front().p; if(!V[3].empty()) b = V[3].front().p; if(!V[4].empty()) c = V[4].front().p; if(a > X) a = stop; if(b > X) b = stop; if(c > X) c = stop; if(a == stop && b == stop && c == stop) break; if((4*a <= 3*b || b == stop) && (6*a <= 4*c || c == stop) && a != stop) { if(a == stop) exit(1); ord.push_back(V[2][0].id); V[2].pop_front(); X -= a; X *= 2; } else if((9*b <= 8*c || c == stop) && b != stop) { if(b == stop) exit(1); ord.push_back(V[3][0].id); V[3].pop_front(); X -= b; X *= 3; } else { if(c == stop) exit(1); ord.push_back(V[4][0].id); V[4].pop_front(); X -= c; X *= 4; } fprintf(stderr, "X = %lld\n", X); search = {X, -1}; ll ac1 = upper_bound(all(p1), X) - p1.begin(); fprintf(stderr, "ac1 = %lld\n", ac1); if(ord.size() + ac1 > ansmax) { ansmax = ord.size() + ac1; t = ord.size(); scegli1 = ac1; } } fprintf(stderr, "\n"); ll ac1 = upper_bound(all(p1), X) - p1.begin(); fprintf(stderr, "ac1 = %lld\n", ac1); if(ord.size() + ac1 > ansmax) { ansmax = ord.size() + ac1; t = ord.size(); scegli1 = ac1; } vector<int> ans; for(int i=0; i<t; i++) ans.push_back(ord[i]); for(int i=0; i<scegli1; i++) ans.push_back(cesti1[i]); return ans; } #ifdef MARCO int main() { int N, A; assert(2 == scanf("%d %d", &N, &A)); std::vector<int> P(N), T(N); for (int i = 0; i < N; i++) assert(2 == scanf("%d %d", &P[i], &T[i])); fclose(stdin); std::vector<int> R = max_coupons(A, P, T); int S = R.size(); printf("%d\n", S); for (int i = 0; i < S; i++) printf("%s%d", (i == 0 ? "" : " "), R[i]); printf("\n"); fclose(stdout); return 0; } #endif

festival.cpp: In function 'std::vector<int> max_coupons(int, std::vector<int>, std::vector<int>)':
festival.cpp:56:50: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   56 |         fprintf(stderr, "==============\nansmax=%d, t=%d, scegli1=%d\n", ansmax, t, scegli1);
      |                                                 ~^                       ~~~~~~
      |                                                  |                       |
      |                                                  int                     long long int
      |                                                 %lld
festival.cpp:56:56: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
   56 |         fprintf(stderr, "==============\nansmax=%d, t=%d, scegli1=%d\n", ansmax, t, scegli1);
      |                                                       ~^                         ~
      |                                                        |                         |
      |                                                        int                       long long int
      |                                                       %lld
festival.cpp:56:68: warning: format '%d' expects argument of type 'int', but argument 5 has type 'long long int' [-Wformat=]
   56 |         fprintf(stderr, "==============\nansmax=%d, t=%d, scegli1=%d\n", ansmax, t, scegli1);
      |                                                                   ~^                ~~~~~~~
      |                                                                    |                |
      |                                                                    int              long long int
      |                                                                   %lld