Speculative Execution (0/100) C++

Aiuto
1

Salve , prima di tutto voglio augurare buona fortuna a tutti per la prossima selezione.
Comunque , il seguente codice funziona in locale (Controllato input e output uguali agli allegati)
Ma durante l’esecuzione sulla piattaforma il risultato e’ 0/100.

#include <iostream>
#include <string>
#include <cstdio>
#define MAXN 100000

using namespace std;
std::string target_var[MAXN];
std::string operand1_var[MAXN];
std::string operand2_var[MAXN];
int N;

int IsInTarget(int pos , string var1,string var2)
{
for(int i = pos ; i!=0 ; i–)
{
if (target_var[i] == var1 || target_var[i] == var2)
return 1;
}
}

int main() {
FILE *fr, *fw;
fr =freopen(“input.txt”,“r”,stdin);
fw =freopen(“output.txt”,“w”,stdout);
int r;
std::cin >> N;
for (int i = 0; i < N; i++) {
char eq, op;
std::cin >> target_var[i] >> eq >> operand1_var[i] >> op >> operand2_var[i];
if (!IsInTarget(i,operand1_var[i],operand2_var[i]))
r++;
}//leggo tutti gli operatori

cout << r ;
return 0;
}

2

A prima vista sembra che il codice sia troppo lento, l’errore che ottieni è execution timed out o output is incorrect?

2 Mi Piace
3

output is incorrect -> Non riesco a capire il motivo …
Per il timed out posso ottimizzarlo :confused:

4 
int r; -> int r = 0;

Non inizializzi r, ad ogni esecuzione del tuo programma è potenzialmente diverso.

Per ottimizzare ti farei notare per prima cosa come il tuo sia un algoritmo \mathcal O(N^2) - per ogni inserimento scorri tutto l’array con i precedenti. Con i limiti del problema ti serve un modo di sapere più rapidamente se una stringa è già stata vista. Puoi usare un std::set<string> per cercare una stringa in \mathcal O(logN) invece che \mathcal O(N)

2 Mi Piace
5

Anche con l’inizializzazione della variabile ho sempre lo stesso problema :confused:

6

Prova a cambiare il typo di eq e op in string, se non sbaglio lo spazio viene considerato come un carattere valido da cin se legge in un char

2 Mi Piace
7

Niente , sempre stessa situazione .

8

Ah, e il loop in IsInTarget dovrebbe avere >= 0 come condizione di continuazione, con != 0 non controllerai mai l’elemento in 0
Aggiungo anche che apri i file di input e output ma non li usi mai

2 Mi Piace
9

freopen mi fa il redirect dell’input all’stdin , se provi il codice in locale funziona con gli esempi dati dal sito.
Quindi teoricamente dovrebbe contarmi la prima task corretta , pero’ viene contata anche quella sbagliata

10

Cambiando un paio di cose sembra funzionare:

  • r = 0;
  • i >= 0
  • manca un return 0; alla fine di IsInTarget, se non ritorna 1 il valore è indefinito
  • Con questa implementazione andrà fuori tempo ben prima, ma MAXN dovrebbe essere 10^6 e non 10^5
3 Mi Piace
11

Ok , ora funziona .
Ti ringrazio , buona giornata!