Ciao,
ti invito a rileggere per bene il testo perché ti sta sfuggendo la richiesta:
i barili sono in fila e quando uno è pieno l’acqua va in quello successivo, quindi non puoi ordinarli per capacità perché l’acqua va messa esattamente nell’i-esimo della fila, non l’i-esimo più grande.
Poi c’è qualche errore nell’impelmentazione:
all’interno del ciclo while hai due possiblità: l’acqua ci sta tutta nel barile corrente (i) oppure no. Hai individuato correttamente questa possibilità ma non l’hai scritto nel modo corretto.
Provo a riscriverla in modo correto.
if(parall[i] < c[i]) {
// temp dice quanta ne rimane dopo che la versi nel barile i-esimo
// k quanta ne metti
int temp = k;
if(k > (c[i] - parall[i])) { // non ci sta tutta nel barile
temp = k;
k = c[i] - parall[i]; // ne puoi mettere solo c[i] - parall[i]
temp -= k;
// ne rimane quella che avevi - quella che riesci a mettere
} else {
temp = 0; // non ne rimane perché ci stava tutta
}
parall[i] += k;
k = temp;
}
Detto ciò, il tuo programma corretto prende 30 punti perché impiega troppo. Per ogni query scorre potenzialmente tutti i barili.
Spoiler: trova un modo di saltare quelli già pieni
Soluzione: puoi usare una DSU
Ok se non sai cosa sia, non ti sarà utile andarla a studiare perché in questo problema viene applicata in maniera un po’ diversa dal suo utilizzo standard.
Non prometto nulla ma potrei scrivere un post prossimamente in cui spiego alcuni utilizzi non banali di quella struttura.
In alternativa, puoi usare un std::set in cui tieni le posizioni dei barili non ancora pieni. In questo modo hai un fattore \log N al posto che \alpha(N) ma funziona ugualmente
Ciao,
vorrei segnalare anche i due variable-length array:
che non sono nello standard C++ e di conseguenza potrebbero causare bug difficili da trovare (parlo per esperienza personale purtoppo). In questo caso non creano problemi (con l’algoritmo giusto puoi fare 100/100 anche con gli array, penso dipenda dal compilatore) ma ti consiglio di abituarti a usare invece metodi standard come std::vector.
Inoltre non capisco perché hai dichiarato le capacità dei barili come long long e il volume effettivo come int, dato che le assunzioni garantiscono per entrambi C_i, k \le 10 ^ 9 < 2 ^ {30} ,
infatti gli int (da standard) sono lunghi almeno 16 bit, ma sono rappresentati quasi sempre a 32 bit, che sono sufficienti.
Ti segnalo che ovviamente il programma viene terminato quando raggiunge il tempo limite, indipendentemente da quanto vicino fosse a terminare.
Quindi se la tua soluzione supera il tempo limite, il tempo mostrato sarà sempre circa 0.1 s oltre il tempo limite. Questo che la tua soluzione impieghi 5 secondi, 1 ora oppure un miliardo di anni a terminare.
Prima sistema il tuo codice in modo che prenda i 30 punti che deve prendere. Poi ti consiglio di fare il problema autogrill di algobadge e vedrai che capirai come usare i set. Buon Natale