32/100 oii riciclo

Ciao a tutti,
Mi trovo in difficolta’ a trovare dei casi limite per questo codice di Riciclo
Attualmente ottiene 32 punti, ovvero tutti i testcase con n < 10000, anche se e’ asintoticamente nei limiti di complessita’
Spero che i tanti commenti non siano fastidiosi

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;

ll res = 0;

// dato la capacita' di un truck ne scinde le potenze di 2
// in c si accumulano le potenze di 2 sommate dei vari truck
// il cap e' necessario quando viene chiamato da collapse
// per evitare che piu' di 2 truck si combinino in una potenza 
// non supportata realmente
void add_truck(ll w, int cap, vector<ll> &c) {
   for (int j = 0; j < 31; j++) {
      if (1 & (w >> j)) {
         // se il bit e' presente in w
         if (j <= cap) c[j]++;
         else c[cap] += 1 << (j-cap);
      }
   }
}

// req: la capacita' richiesta misurata in numero di pallet, non peso reale
// base: indica l'indice da cui e' partita req
// pos: indica l'indice da cui si va ad attingere potenza
// c: somma dei bit dei singoli truck
// p: array dei pallet
void collapse(ll req, int base, int pos, vector<ll>& c, vi& p) {
   // per evitare l'out of range
   if (pos == 31) return;
   // q: portata misurata con la stessa potenza di req
   ll q = c[pos] << (pos-base);
   c[pos] = 0;
   if (req > q) {
      // se la richiesta non supera la portata allora si ricorre 
      // a una potenza superiore, togliendo dalla richiesta il disponibile
      req -= q;
      res += q;
      collapse(req, base, pos+1, c, p);
   }
   else {
      // la disponibilita' corrente e' azzerata
      // cio' che rimane dopo aver tolto la req e' reintrodotto come altro truck
      res += req;
      add_truck((q-req) << base, pos, c);
   }
}

ll riciclo(int n, int m, vi t, vi p) {
   vector<ll> c(31, 0);
   for (int i = 0; i < n; i++)
      // 34 e' arbitrario per non raggiungere il cap
      add_truck(t[i], 34, c);
   for (int j = 0; j < m; j++)
      // i carichi di potenza minore hanno precedenza
      // assoluta su quelli maggiori
      // non si aumenta la dimensione del carico prima 
      // di aver terminato quelli ti peso minore
      collapse(p[j], j, j, c, p);
   return res;
}

Analizzando il tuo codice l’unica cosa che non mi convinceva era l’uso della add_truck() dentro la collapse(), ho modificato questa parte che riscompone il resto in potenze di 2 e riaggiorna c e ha funzionato.
In particolare non mi convinceva l’uso di cap al suo interno. Se vuoi ti posto le modifiche.

Credo di aver capito cosa non funzionasse
Ho aggiunto il cap quando ho notato che c, che era …0 0 3 0, dopo add_truck diventava …0 1 1 0, dunque per limitare la conversione della potenza piu’ alta, pero’ noto ora che il cap non limita la “aggregazione” delle potenze piu’ basse
Mi piacerebbe vedere le modifiche perche’ non penso sarei in grado di scrivere qualcosa di anche lontanamente pulito
Intanto grazie mille

Ecco le modifiche, anche queste non sono granché pulite.

else {
        // la disponibilita' corrente e' azzerata
        // cio' che rimane dopo aver tolto la req e' reintrodotto come altro truck
        res += req;
        // parte nuova
        long long x = (q - req) << base;
        long long div= x >> pos;
        c[pos] = div;
        long long spez = x % pot2[pos];
        add_truck(spez, pos, c);
        // parte vecchia
        //add_truck((q - req) << base, pos, c);//base
    }

I bit di spez dovrebbero essere meno significativi di pos e quindi pos non dovrebbe servire!
Inoltre ho usato la tabella delle prime 31 potenze di 2 (pot2[] presa dalla mia soluzione)

provato la nuova add_truck() e va:

void add_truck(ll w,  vector<ll>& c) {//int cap,
    for (int j = 0; j < 31; j++) {
        if (1 & (w >> j)) {
            c[j]++;
           
        }
    }
}

p.s.
entra anche in classifica