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;
}