Aiuto per Playing with barrels (ois_barrels)

ciao a tutti! Probabilmente avrò fatto degli erroracci, ma non mi viene proprio in mente cosa possa aver sbagliato.

#include<bits/stdc++.h>
using namespace std;

bool comp(int a, int b){
	return a>b;
}

int main() {

     //freopen("input.txt", "r", stdin);
     //freopen("output.txt", "w", stdout);
    
    int n,t;  //numero di barili e numero di mosse
    char move;
    int k,q,u;   //litri versati e posizione barile
    
    cin>>n>>t;
    long long c[n];
    int parall[n]; // capienza barili
    for(int i=0; i<n; i++){
    	cin>>c[i];
    	parall[i] = 0;
	}
    sort(c,c+n,comp);
	for(int j = 0; j<t; j++){
		cin>>move;
		if(move == 'P'){
			cin>>k>>u;
			int i = u;
			while(k>0 && i<n){
				if(parall[i] <c[i]){
				int temp = k;
					if(k>(c[i]-parall[i])){
						temp=k;
						k = abs(k-(c[i]-parall[i]));
						temp-=k;
					}
					parall[i]+=k;
					k = temp;
				}
				i++;
			}
		}
		else{
			cin>>q;
			cout<<parall[q]<<endl;
		}
	}    

	   return 0;
}

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

non so cosa sia :sweat_smile:
vado a guardarmela e vedo un po’!

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.

va bene anche un vector? non ho molta familiarità coi set

sisi quelle le avevo sistemate, il problema è qualche centesimo di sec che manda in overtime

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.

1 Mi Piace

mm…
vuol dire che lo lascerò in sospeso fino a quando non saprò usare i set o la DSU

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

okok, ho corretto per i 30. Ora vedo autogrill.
Buon Natale anche a voi!

1 Mi Piace