# Pesci Mangioni(ois\_pesci)

**URL:** <https://forum.olinfo.it/t/pesci-mangioni-ois-pesci/6163>\
**Category:** Aiuto\
**Created:** [22 Aprile 2020, 4:14pm UTC](https://forum.olinfo.it/t/pesci-mangioni-ois-pesci/6163 "2020-04-22T16:14:15Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\
**Post date:** [22 Aprile 2020, 4:14pm UTC](https://forum.olinfo.it/t/pesci-mangioni-ois-pesci/6163/1 "2020-04-22T16:14:15Z")

</div>

Mi servirebbe un aiuto con questo problema perché penso di non aver capito bene cosa chiede il problema io pensavo di averlo risolto da ciò che avevo capito, però al quanto pare mi sbagliavo.

```auto
#include <bits/stdc++.h>
using namespace std;
int main(){
   freopen("input.txt","r",stdin);
   freopen("output.txt","w",stdout);
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   int N,vivi=0;
   cin>>N;
   vector<pair<int,int>>v(N);
   vector<bool>contr(N);
   for(int i=0;i<N;i++){
   	cin>>v[i].first>>v[i].second;
   	contr[i]=false;
   }
   bool A=true;
   for(int i=0;i<N && A==true;i++){
   	if(v[i].first==1){
   		vivi++;
   		contr[i]=true;
   	}
   	else{
   		A=false;
   	}
   }
   A=true;
   for(int i=N-1;i>=0 && A==true && contr[i]==false;i--){
   	if(v[i].first==0){
   		vivi++;
   		contr[i]=true;
   	}
   	else{
   		A=false;
   	}
   }
   stack<int>zero,uno;
   for(int i=0;i<N;i++){
   	if(contr[i]==false){
   		if(v[i].first==1){
   			uno.push(v[i].second);
   		}
   		else{
   			zero.push(v[i].second);
   		}
   	}
   }
   while(zero.empty()==false && uno.empty()==false){
   	if(zero.top()>uno.top()){
   		uno.pop();
   	}
   	else{
   		zero.pop();
   	}
   }
   cout<<vivi+zero.size()+uno.size();
}

```

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [23 Aprile 2020, 7:52am UTC](https://forum.olinfo.it/t/pesci-mangioni-ois-pesci/6163/2 "2020-04-23T07:52:12Z")

</div>

Non mi convince molto l’idea dei due stack, infatti perdi informazioni sulla posizione dei pesci con direzione 0 rispetto a quelli con direzione 1. Prova a vedere questi 2 casi:

```auto
3
0 2
1 1
1 3

3
0 2
1 3
1 1

```

Il tuo programma sbaglia in entrambi perché crede che `0 2` si scontrerà prima con l’ultimo.

---

<div class="post-metadata">

**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\
**Post date:** [23 Aprile 2020, 8:28am UTC](https://forum.olinfo.it/t/pesci-mangioni-ois-pesci/6163/3 "2020-04-23T08:28:55Z")

</div>

Allora forse non ho chiaro in che ordine vengono inseriti  
Nel caso i dati siano:

```auto
7
1 3
0 6
0 2
1 4
0 1
1 7
0 10

```

Nel tubo vengono inseriti cosi(le freccie sono le direzioni):

```auto
3 6 2 4 1 7 10
< > > < > < >

```

Da ciò che ho capito io dovrebbe accadere questo:  
(il numero non è la posizione è il peso)

3 non incontra nessuno quindi si salva  
10 stesso discorso del 3 si salva anche lui  
il 4 mangia il 2  
il 6 mangia il 4  
il 7 mangia sia l’1 che il 6

Per ciò ne rimangono 3 in vita:  
il 10, il 3 e il 7

è giusto oppure ho capito male io?

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [23 Aprile 2020, 9:24am UTC](https://forum.olinfo.it/t/pesci-mangioni-ois-pesci/6163/4 "2020-04-23T09:24:22Z")

</div>

Eh è giusto, ma il tuo programma dà 4 in output

---

<div class="post-metadata">

**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\
**Post date:** [23 Aprile 2020, 4:45pm UTC](https://forum.olinfo.it/t/pesci-mangioni-ois-pesci/6163/5 "2020-04-23T16:45:54Z")

</div>

Grazie finalmente ho capito l’errore era veramente banale ora ho un ultimo problema va in timeout negli ultimi tre casi  
Questo è la mia soluzione:

```auto
#include <bits/stdc++.h>
using namespace std;
vector<int>zero,zero_i,uno,uno_i;
int lower(int n){
   int i=0;
   int min=-1;
   if(zero_i[0]>n){
   	return -1;
   }
   while(zero_i[i]<n && i<zero_i.size()){
   	min=i;
   	i++;
   }
   return min;
}
int main(){
   int N,vivi=0;
   cin>>N;
   vector<pair<int,int>>v(N);
   vector<bool>contr(N);
   for(int i=0;i<N;i++){
   	cin>>v[i].first>>v[i].second;
   	if(v[i].first==0){
   		zero.push_back(v[i].second);
   		zero_i.push_back(i);
   	}
   	else{
   		uno.push_back(v[i].second);
   		uno_i.push_back(i);
   	}
   	contr[i]=false;
   }
   bool A=true;
   for(int i=0;i<N && A==true;i++){
   	if(v[i].first==1){
   		uno.erase(uno.begin());
   		uno_i.erase(uno_i.begin());
   		vivi++;
   		contr[i]=true;
   	}
   	else{
   		A=false;
   	}
   }
   A=true;
   for(int i=N-1;i>=0 && A==true && contr[i]==false;i--){
   	if(v[i].first==0){
   		zero.erase(zero.end()-1);
   		zero_i.erase(zero_i.end()-1);
   		vivi++;
   		contr[i]=true;
   	}
   	else{
   		A=false;
   	}
   }
   while(zero.empty()==false && uno.empty()==false){
   	int val=*uno_i.begin();
   	int num;
   	if(lower(val)==-1){
   		uno.erase(uno.begin());
   		uno_i.erase(uno_i.begin());
   		vivi++;
   	}
   	else{
   		num=lower(val);
   		if(uno[0]>zero[num]){
   			zero.erase(zero.begin()+num);
   			zero_i.erase(zero_i.begin()+num);
   		}
   		else{
   			uno.erase(uno.begin());
   			uno_i.erase(uno_i.begin());
   		}
   	}
   }
   cout<<vivi+zero.size()+uno.size();
}

```

Ho provato a usare anche lower\_bound e upper\_bound per cercare l’elemento minimo al posto di usare la funzione lower ma ho avuto qualche problema e l’ho accantonata

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [23 Aprile 2020, 6:00pm UTC](https://forum.olinfo.it/t/pesci-mangioni-ois-pesci/6163/6 "2020-04-23T18:00:53Z")

</div>

Ho dato uno sguardo veramente veloce ma vedo che fai degli erase su un vector, sebbene sia una funzione molto veloce ha comunque una complessità lineare (in quanto deve spostare tutti gli elementi che si trovano tra quello eliminato e la fine), quindi la complessità del tuo algoritmo diventa N^2, che è troppo per le assunzioni del problema. Anche la funzione lower è lineare se non sbaglio, devi cercare di cambiare queste funzioni con qualcosa di più efficiente.

---

<div class="post-metadata">

**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\
**Post date:** [23 Aprile 2020, 8:48pm UTC](https://forum.olinfo.it/t/pesci-mangioni-ois-pesci/6163/7 "2020-04-23T20:48:55Z")

</div>

Potrebbe andar bene usare un lower\_bound al posto della funzione lower, ed a proposito di questo, se io voglio fare la ricerca con lower\_bound partendo dalla fine del vettore si puo fare una cosa del genere:

```auto
sort(v.begin(),v.end());
lower_bound(v.rbegin(),v.rend(),num);

```

Perchè ho la sensazione che ,dal momento che il vettore è ordinato in maniera crescente,facendo in controllo partendo dalla fine posso dare problemi.

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [24 Aprile 2020, 7:58am UTC](https://forum.olinfo.it/t/pesci-mangioni-ois-pesci/6163/8 "2020-04-24T07:58:29Z")

</div>

Purtroppo non conosco bene il comportamento del lower\_bound con i reverse iterator ma immagino che vada inclusa la funzione `greater<int>`

```auto
lower_bound(v.rbegin(),v.rend(),num,greater<int>());

```

Non so aiutarti oltre dato che io farei un lower\_bound semplice con un controllo alla fine, magari è meglio la tua idea però.

---

<div class="post-metadata">

**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\
**Post date:** [24 Aprile 2020, 8:23am UTC](https://forum.olinfo.it/t/pesci-mangioni-ois-pesci/6163/9 "2020-04-24T08:23:01Z")

</div>

Ok grazie mille ora provo in un paio di modi