Pesci Mangioni(ois_pesci)

Aiuto
1

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.

#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();
}
2

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:

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.

3

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

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):

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?

4

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

5

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:

#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

6

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.

7

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:

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.

8

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

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ò.

9

Ok grazie mille ora provo in un paio di modi