Musical Fight not working

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
    
int N, L,result[5000];
vector<string> aghi,temp;

bool inArray(string &value, vector<string> &array){ //funzione per cercare un elemento in un array di stringhe
    return find(array.begin(), array.end(), value) != array.end();
}
void clearArray(int M){             //funzione per rimuovere gli elementi che compaiono
    sort(temp.begin(),temp.end());  //più di una volta, questa funzione blocca
    for(int asd=0;asd<M;asd++){      //tutto il programma
        for(int dsa=asd+1;dsa<M;dsa++){
            while(temp[dsa]==temp[asd])temp.erase(temp.begin()+dsa);
        }
    }
}

int main() {
//  uncomment the following lines if you want to read/write from files
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    cin >> N >> L;
    int naghi; cin>>naghi; aghi.resize(naghi); 
    for(int i=0;i<naghi;i++){
        cin>>aghi[i];
    }
    for (int i=0; i<N-1; ++i) {
        int M;
        cin >> M; temp.resize(M);
        for (int j=0; j<M; ++j){cout<<1;cin>>temp[j];}
        clearArray(M);
        for(int x=0;x<naghi;x++){
            if(inArray(aghi[x],temp)){
                result[x]++;
            }
        }
        cout<<endl;
    }
    for(int x=0;x<naghi;x++){
        int sos=x-1;
        while(aghi[sos]!=aghi[x]&&sos>=0)sos--;
        if(sos>=0)result[x]=result[sos];
    }
    for(int g=0;g<naghi;g++){
        cout<<result[g]<<" ";
    }
    return 0;
}

non riesco a capire perchè il programma si ferma e non continua con l’esecuzione del programma, l’errore che ottengo eseguendo il debug è il seguente: <error reading variable: Cannot create a lazy string with address 0x0, and a non-zero length.>

Ciao, con queste poche informazioni è difficile aiutarti.

Si tratta solo di un errore del debugger?
Se non usi il debugger funziona?
In quale punto dell’esecuzione viene generato l’errore?
Qual è l’output completo del debugger?
Quale compilatore/debugger/IDE stai usando?
Hai provato a cercare l’errore su google?

Si tratta solo di un errore del debugger?
si
Se non usi il debugger funziona?
si ferma nella funzione clear array e non prosegue il programma, senza dare alcun errore
In quale punto dell’esecuzione viene generato l’errore?
Qual è l’output completo del debugger?
std::vector of length -1, capacity 6 = {“mi”, “nisti”, “nisti”, “”, “”, “”, <error reading variable: Cannot create a lazy string with address 0x0, and a non-zero length.>
Quale compilatore/debugger/IDE stai usando?
ne uso uno online
Hai provato a cercare l’errore su google ?
si, non ho trovato risposta, nel link non danno alcuna informazione su come risolverlo

Ho provato il tuo codice sotto debug e ci sono problemi di indici che vanno fuori della gamma corretta:
(da 0 a temp.size()-1) ad esempio.

void clearArray(int M){             //funzione per rimuovere gli elementi che compaiono
    sort(temp.begin(),temp.end());  //più di una volta, questa funzione blocca
    for(int asd=0;asd<M;asd++){      //tutto il programma
        for(int dsa=asd+1;dsa<M;dsa++){
            while(temp[dsa]==temp[asd])temp.erase(temp.begin()+dsa);
        }
    }
}

quando elimini un elemento l’estremo superiore non è più M ma M-1. (sostituisci a M temp.size())
(Il primo ciclo dovrebbe andare fino a temp.size()-1)
Come se la cava:
while(temp[dsa]==temp[asd])temp.erase(temp.begin()+dsa);
quando hai a che fare con stringhe tutte uguali? ne rimarrà una sola e quindi la seconda non esisterà.
infine
while(aghi[sos]!=aghi[x]&&sos>=0)sos–;
va scritta
while(sos>=0 && aghi[sos]!=aghi[x])sos–;
altrimenti aghi[sos] viene valutato anche con sos<0.

Tolti questi errori purtroppo vengono fuori gli “execution timed out” ed il programma riesce comunque a fare 27 punti.

P.S.
Fai il sort di temp ma poi non lo sfrutti per la ricerca dei duplicati!?
ci sono un pò di cout da togliere
Migliorando (rifacendo) la clearArray() e usando la ricerca binaria nella inArray() la tua soluzione arriva a 79/100. (time out solo sull’ultimo subtask)

Grazie mille per i consigli, adesso provo. Mi conviene non tenere in considerazione la L(il numero massimo di caratteri di cascuna parola)? Pensavo che l’esercizio fosse un po’ vecchio e che magari quella serviva per dare le dimensioni agli Array di char.

Adesso lavoraci sopra, poi se vuoi ho altri consigli. Per quanto riguarda L almeno adesso lascialo pure da parte.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

// input data
int N, L;
string aghi[5000],temp;
vector<string> aghiOrdinati;
vector<int> result;
vector<string>::iterator p;

int main() {
//  uncomment the following lines if you want to read/write from files
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int naghi;
    cin >> N >> L>>naghi;
    aghiOrdinati.resize(naghi);
    for(int i=0;i<naghi;i++){
        cin>>aghi[i];
        aghiOrdinati[i]=aghi[i];
    }
    sort(aghiOrdinati.begin(),aghiOrdinati.begin()+naghi);
    for(int i=naghi-1;i>0;i--){
        while(i>0&&aghiOrdinati[i]==aghiOrdinati[i-1]){
            aghiOrdinati.erase(aghiOrdinati.begin()+i); i--;
        }
    }
    result.resize(aghiOrdinati.size());
    for(int i=0;i<aghiOrdinati.size();i++)
        result[i]=0;
    for (int i=0; i<N-1; ++i) {
        int M;
        cin >> M;
        bool usato[5000]={};
        for (int j=0; j<M; ++j) {
            cin>>temp;
            p=find(aghiOrdinati.begin(),aghiOrdinati.end(),temp);
            if(p!=aghiOrdinati.end()){
                int index=distance(aghiOrdinati.begin(),p);
                if(!usato[index]){
                    result[index]++;
                    usato[index]=true;
                }
            }
        }
    }
    for(int i=0;i<naghi;i++){
        cout<<result[distance(aghiOrdinati.begin(),find(aghiOrdinati.begin(),aghiOrdinati.end(),aghi[i]))]<<" ";
    }
    return 0;
}

con questo codice sono riuscito a ottenere 79/100, tuttavia non riesco nemmeno a pensare un metodo per risolvere questo problema più veloce, a parte usare gli array di char, che comunque non mi permetterebbero di raggiungere la velocità richiesta.

Con le stringhe lunghe al massimo 10 caratteri puoi associare un numero x (long long) ad ogni stringa e lavorare con quello al posto della stringa.

la find è troppo lenta non sfrutta il fatto che aghiOrdinati è, per l’appunto, ordinata ci vuole una ricerca binaria che ti puoi anche scrivere da solo e che calcola direttamente index e si fa 100. (va usata anche nella stampa)

ho ottenuto 100/100 alla fine, ho reinviato lo stesso codice più volte finchè non è uscito corretto, questo è il codice:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

// input data
int N, L,mid;
string aghi[5000],temp;
vector<string> aghiOrdinati;
vector<int> result;
//vector<string>::iterator p;

int binarySearch(int inizio,int fine){
    while(fine>=inizio){
        mid=(inizio+fine)/2;
        if(aghiOrdinati[mid]==temp)return mid;
        if(aghiOrdinati[mid]>temp)fine=--mid;
        else inizio=++mid;
    }
    return -1;
}

int main() {
//  uncomment the following lines if you want to read/write from files
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int naghi;
    cin >> N >> L>>naghi;
    aghiOrdinati.resize(naghi);
    for(int i=0;i<naghi;i++){
        cin>>aghi[i];
        aghiOrdinati[i]=aghi[i];
    }
    sort(aghiOrdinati.begin(),aghiOrdinati.begin()+naghi);
    for(int i=naghi-1;i>0;i--){
        while(i>0&&aghiOrdinati[i]==aghiOrdinati[i-1]){
            aghiOrdinati.erase(aghiOrdinati.begin()+i); i--;
        }
    }
    result.resize(aghiOrdinati.size());
    for(int i=0;i<aghiOrdinati.size();i++)
        result[i]=0;
    for (int i=0; i<N-1; ++i) {
        int M;
        cin >> M;
        bool usato[5000]={};
        for (int j=0; j<M; ++j) {
            cin>>temp;
            int index=binarySearch(0,aghiOrdinati.size()-1);
            if(index!=-1&&!usato[index]){
                result[index]++;
                usato[index]=true;
            }
            /*p=find(aghiOrdinati.begin(),aghiOrdinati.end(),temp);
            if(p!=aghiOrdinati.end()){
                int index=distance(aghiOrdinati.begin(),p);
                if(!usato[index]){
                    result[index]++;
                    usato[index]=true;
                }
            }*/
        }
    }
    for(int i=0;i<naghi;i++){
        cout<<result[distance(aghiOrdinati.begin(),find(aghiOrdinati.begin(),aghiOrdinati.end(),aghi[i]))]<<" ";
    }
    return 0;
}

Bene e già che ci sei perchè

e non
cout << result[binarySearch(aghi[i])] << ’ ';

Però devi riadattare i parametri della binarySearch:
i parametri che gli passi sono inutili (la funzione è capacissima di trovarseli da sola) e così com’è lavora solo su temp, passagli soltanto la stringa da cercare e potrai usarla anche per le stampe.

Inoltre ho visto che i tempi si abbassano apprezzabilmente se usi un

vector<string> aghiOrdinati[11];

e separi le stringhe in base alla loro lunghezza adesso provo a farlo anche sulla mia soluzione.

dopo provo ad aggiornare il codice aggiungendo
vector<string> aghiOrdinati[11]; e dividendo in base alla lunghezza

per il cout mi sono dimenticato di aggiornarlo dopo aver aggiunto la funzione binarySearch(all’inizio avevo fatto una funzione ricorsiva, per quello usavo i parametri, poi mi sono dimenticato di aggiornare)

Migliorie:
Propongo questa binarySearch:

int binarySearch(string temp){
    int inizio=0;
    int fine=aghiOrdinati.size()-1;
    int r;
    while(fine>=inizio){
        mid=(inizio+fine)>>1;
        r=aghiOrdinati[mid].compare(temp);
        if(!r)
           return mid;
        if(r>0) fine=--mid;
        else inizio=++mid;
    }
    return -1;
}

la compare fra stringhe viene eseguita una sola volta.

for(int i=naghi-1;i>0;i--){
        while(i>0&&aghiOrdinati[i]==aghiOrdinati[i-1]){
            aghiOrdinati.erase(aghiOrdinati.begin()+i); i--;
        }
    }

La erase() è estremamente lenta, per eliminare un elemento scorre a sinistra di una posizione tutti gli elementi che lo seguono. (si possono eseguire tutte le cancellazioni con un unico scorrimento).

Comunque la tua ultima versione con la binarySearch() scritta sopra ed usata anche per le stampe dei risultati e con le seguenti aggiunte:

#pragma GCC optimize ("Ofast") 
#pragma GCC optimization ("unroll-loops")
..
ios_base::sync_with_stdio(false);
cin.tie(NULL);

fa stabilmente 100.
Se vuoi te la mando.

in teoria dovrei aver aggiunto tutto correttamente (esclusa la sostituzione ad erase che non saprei cosa mettere), ma mi farebbe piacere comunque vedere la soluzione per vedere se ho sbagliato qualcosa.

Eccola:

#pragma GCC optimize ("Ofast") 
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

// input data
int N, L, mid;
string aghi[5000], temp;
vector<string> aghiOrdinati;
vector<int> result;
//vector<string>::iterator p;

int binarySearch(string temp) {
    int inizio = 0;
    int fine = aghiOrdinati.size() - 1;
    int r;
    while (fine >= inizio) {
        mid = (inizio + fine) >> 1;
        r = aghiOrdinati[mid].compare(temp);
        if (!r)
            return mid;
        if (r > 0) fine = --mid;
        else inizio = ++mid;
    }
    return -1;
}

int main() {
    //  uncomment the following lines if you want to read/write from files
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int naghi;
    cin >> N >> L >> naghi;
    aghiOrdinati.resize(naghi);
    for (int i = 0; i < naghi; i++) {
        cin >> aghi[i];
        aghiOrdinati[i] = aghi[i];
    }
    sort(aghiOrdinati.begin(), aghiOrdinati.begin() + naghi);
    /*
    for (int i = naghi - 1; i > 0; i--) {
        while (i > 0 && aghiOrdinati[i] == aghiOrdinati[i - 1]) {
            aghiOrdinati.erase(aghiOrdinati.begin() + i); i--;
        }
    }
    result.resize(aghiOrdinati.size());
    */
// l'alternativa all'uso della erase
    int j = 0;
    for (int i = 1; i < naghi; i++) {
        if (aghiOrdinati[i].compare(aghiOrdinati[j]))
            aghiOrdinati[++j] = aghiOrdinati[i];
    }
    aghiOrdinati.resize(j + 1);
    result.resize(j+1);
    //for(int i=0;i<aghiOrdinati.size();i++)  // non serve
    //    result[i]=0;
    for (int i = 0; i < N - 1; ++i) {
        int M;
        cin >> M;
        bool usato[5000] = {};
        for (int j = 0; j < M; ++j) {
            cin >> temp;
            int index = binarySearch(temp);
            if (index != -1 && !usato[index]) {
                result[index]++;
                usato[index] = true;
            }
            /*p=find(aghiOrdinati.begin(),aghiOrdinati.end(),temp);
            if(p!=aghiOrdinati.end()){
                int index=distance(aghiOrdinati.begin(),p);
                if(!usato[index]){
                    result[index]++;
                    usato[index]=true;
                }
            }*/
        }
    }
    for (int i = 0; i < naghi; i++) {
        cout << result[binarySearch(aghi[i])] << " ";
        //cout<<result[distance(aghiOrdinati.begin(),find(aghiOrdinati.begin(),aghiOrdinati.end(),aghi[i]))]<<" ";
    }
    return 0;
}

capito, grazie mille, sia per le spiegazioni che i consigli, mi sono stati molto d’aiuto.