Submission #1314722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314722		marcogambaro	Festival (IOI25_festival)	C++20	32 / 100	504 ms	22140 KiB

festival

#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

Compilation message (stderr)

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

• Subtask 0: 0 / 0
• Subtask 1: 5 / 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