Salve a tutti,
Ho provato a risolvere l’algoritmo dell’esercizio " pesci mangioni " ma ottengo solo 3 output corretti e il 10/100 del punteggio.
Qui trovate il codice : https://pastebin.com/LcHhDaKS.
Grazie 
Se non ho capito male tu quando trovi 2 pesci adiacenti che nuotano in direzione opposta elimini il più piccolo, ma se quello più a sinistra dei due si muove verso sinistra e quello più a destra va verso destra, vanno in direzioni diverse eppure non si mangiano
Quando usi la funzione erase elimini un elemento e quindi la dimensione del vector si riduce, però tu vai a chiamare elementi che non dovrebbero esistere.
Un modo per risolvere sarebbe sostituire nel for i<N con i<j e ogni volta che elimini un elemento decrementare i.
Tuttavia la funzione erase ha complessità \mathcal O(N) e quindi la soluzione finale diventa \mathcal O(N^2) che -teoricamente- dovrebbe andare fuori tempo.
Prova a pensare un modo per cancellare un elemento in \mathcal O(1).
Se lo cancellellassi dal fondo o dalla cima?
Ho cambiato l’if della direzione in questo modo:
if(direzione[i] != direzione[i-1] && (direzione[i] != 0 && direzione[i-1] != 1)) { ... }
E la condizione di uscita del ciclo da i<N a i<j pero’ ottengo qualche output corretto in piu’ nel 2 subtask, ma ottengo sempre il 10/100.
Come ho già detto prima, anche se l’algoritmo fosse giusto andrebbe fuori tempo, quindi prova a cambiare strategia.
Sei sicuro che basti una passata? Prova a simulare, anche se comunque effettivamente il tuo approccio è troppo lento
Voi come l’avete fatto ?
L’ideale sarebbe quello di usare una pila scorrendo i pesci verso destra, se i pesci vanno verso destra li aggiungi, altrimenti elimini dalla cima finché i pesci non si sono mangiati a vicenda seguendo le regole. La risposta del problema è la dimensione della pila. Le funzioni pop e push sono entrambe costanti, quindi la soluzione finale diventa \mathcal O(N).
Io ci avevo ragionato qualche giorno fa, ma non ho avuto voglia di implementarlo , ma l’avevo ragionato così:
Nel caso in cui il pesce più a sinistra va a sinistra lo tolgo e aggiungo a quelli che rimarranno, stessa cosa per quello verso destra.
Se i 2 più verso sinistra vanno verso destra ed è più piccolo dei due il più verso sinistra allora quel pesce avrà la stessa sorete del secondo e quindi è come se il secondo valese 2 pesci
Se invece il più a sinistra va verso destra e il secondo più a sinistra va verso sinistra elimino il più piccolo se invece sia il più a sinistra che il secondo più a sinistra vanno verso destra e il più a sinistra è più grande allora sposto il ragionamento sul secondo
Spero di non aver fatto confusione
L’idea mi sembra ottima…
Il codice andrebbe fatto così ? (https://pastebin.com/urAcnGyD)
Ti manca la parte in cui i pesci si mangiano a vicenda.
Se il pesce va verso destra lo aggiungo alla pila e fin qua è chiaro, se va verso sinistra devo controllare quanti pesci riesce a mangiare prima di essere mangiato a sua volta o di aver mangiato tutti i pesci della pila.
Quando capisci il concetto l’implementazione risulta semplice.
L’array direzione, indicizzato da 0 a N − 1, indica se l’i−esimo pesce nuota da sinistra verso destra (direzione[i]= 0) o da destra verso sinistra (direzione[i]= 1).
Fai attenzione a destra e sinistra.
Non avendo mai usato una pila in c++, non riesco a fare la parte del codice in cui va verso sinistra…
La pila è piuttosto semplice da usare.
Ha due operazioni in \mathcal O(1) aggiungere un elemento alla cima (push) e rimuovere un elemento dalla cima (pop), inoltre si può accerere solo all’elemento in cima (top). Queste tre funzioni sono sufficienti per risolvere il problema.
Ecco un esempio:
stack<int> s;
s.push(3);
s.push(2);
s.push(5);
cout << s.top(); // 5
s.pop();
cout << s.top(); // 2
Se preferisci puoi usare al posto della pila un vector basta sostituire le funzioni: push -> push_back, pop -> pop_back e top -> back e il funzionamento è identico.
Detto questo, quando trovi un pesce P_i che va a sinistra devi eliminare il pesce in cima fino a quando quest’ultimo è più grande di P_i oppure la pila è vuota (ricordati che se la pila è vuota devi aggiungere il pesce P_i alla pila poiché non viene mangiato da nessuno), è piuttosto semplice.
Grazie delle spiegazioni… sei stato molto gentile…
Per caso intendi questo " https://pastebin.com/pLLPwvNs " ?
Sei sulla giusta strada! 
Basta qualche piccola correzione:
-
All’interno del for manca l’else
-
s.top() > dimensione[i]dovrebbe essere minore e non maggiore -
Non consideri il caso in cui all’interno della pila vi siano pesci che vanno verso sinistra, poiché un pesce che arriva da sinistra, se è più grande se lo mangerebbe.
I primi due punti sono semplici da correggere, per l’ultimo è un po’ più complicato, ci sono essenzialmente 3 modi per risolverlo:
-
Eviti di aggiungere i pesci che vanno verso sinistra e utilizza un’altra variabile (per esempio
j) per tenerti conto di questi pesci e la soluzione diventerebbes.size() + j -
Utilizzi uno stack di pair
-
Ti crei la tua struttura dati
L’ultima scelta è la più complessa, ma risulta davvero utile negli esercizi più difficili, diventa una cosa di questo tipo:
struct pesce{
int peso; //dimesione
int verso; //direzione
};
Se usi invece la prima soluzione devi stare attento ad una cosa: quando chiami s.top() e la pila è vuota ti dà errore, un modo per correggere è inserire un numero molto grande all’inizio (come può essere INT_MAX della libreria <climits>) e invece di utilizzare s.empty() utilizzi s.size() == 1 e poi alla fine decrementi il totale di 1. E’ più complicato di quel che pensavo quindi se non hai voglia di provare da solo e per non tirare troppo avanti l’argomento ecco qua:
stack<int> s;
int j = -1;
s.push(INT_MAX);
for(int i=0; i<N; i++)
{
if (direzione[i] == 1)
{
while (s.top() < dimensione[i])
s.pop();
if (s.size() == 1)
j++;
}
else
s.push(dimensione[i]);
}
return s.size() + j;
Se non riesci a copiare vai qua.
Se invece desideravi trovare una soluzione con la struttura dati te la lascio qua.
Spero di essere stato utile e chiaro, questo problema era un po’ particolare, spero che almeno hai capito il concetto che c’era dietro la soluzione e se hai qualche domanda chiedi pure 
Volevo provare la tua soluzione ma molti dei subtask risultano sbagliati, con “Execution killed with signal 11 (could be triggered by violating memory limits)”, non riesco a capire dove è l’errore visto che quando esegui l’istruzione pop verifichi prima che lo stack non sia vuoto
Ho provato le soluzioni e funzionavano 
EDIT: no hai ragione tu, devo aver confuso un po’ di cose, il problema è qua:
while (s.top().peso < dimensione[i] && !s.empty() && s.top().verso == 0)
quando accedi a top se è vuoto ti dà errore, il problema è che tu controlli se è vuoto dopo avere chiamato top, così dovrebbe funzionare:
while (!s.empty() && s.top().peso < dimensione[i] &&s.top().verso == 0)
Non avevo fatto caso all’ordine 