Lotteria di quadri aiuto "Execution killed (could be triggered by violating memory limits)"

Aiuto
1

quasi tutti i tasktest mi danno l’errore “Execution killed (could be triggered by violating memory limits)” , ma nessuno dei 35 supera 1MiB di memoria (max: 64MiB), il codice è questo

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <set>
#include <numeric>

static FILE *fr, *fw;

// Declaring variables
static int N;
static long long M;
static int* V;
static int B;

int quadri(int N, long long M, int V[]) {
    int B = 2*N;
    long long int c = 0, g = 0;
    std::multiset<long long int, std::greater<long long int>> vb;
    
    //qua controllo se il valore del quadro più costoso è più grande di M, la funzione risulta 0
    for (int i = 0; i < N-1; i++){
        if (V[i] > g) g = V[i];
    }
    if (g>M) return 0;
    
    //qua dimezzo il valore di B, faccio tutti i gruppi possibili di grandezza B e vedo se la loro somma supera M
    //se lo fa, allora ricomincio, se non lo fa vado avanti
    do{
        B /= 2;
        c = 0;
        vb.clear();
        for (int i = 0; i <N-B; i++){
            vb.insert(std::accumulate(V + c, V + c + B + 1, 0));
            c++;
        }
    }while(*vb.rbegin()>M);
    
    //qua vedo di quella metà di troppo che ho dimezzato, in quale valore di B si aveva il risultato corretto
    do{
        B++;
        c = 0;
        vb.clear();
        for (int i = 0; i <N-B; i++){
            vb.insert(std::accumulate(V + c, V + c + B + 1, 0));
            c++;
        }
    }while(*vb.rbegin()>M);


    return B;
}

int main() {
	fr = stdin;
	fw = stdout;

	// Iterators used in for loops
	int i0;

	// Reading input
	fscanf(fr, "%d %lld", &N, &M);
	V = (int*)malloc(N * sizeof(int));
	for (i0 = 0; i0 < N; i0++) {
	    fscanf(fr, "%d", &V[i0]);
	}

	// Calling functions
	B = quadri(N, M, V);

	// Writing output
	fprintf(fw, "%d\n", B);

	fclose(fr);
	fclose(fw);
	return 0;
}
2

Non ho letto il codice ma di solito quando vai in mle senza mostrare molta memoria utilizzata è perchè accedi a posizioni che non esistono

3

Ciao, il problema nel tuo codice è l’accesso a posizioni nello std::multiset che non esistono realmente – in altre parole stai cercando di accedere ad elementi che non sono contenuti all’interno della struttura dati (quindi situati al di fuori della memoria allocata per la variabile vb). Sistemando questo problema il programma non va più in MLE, tuttavia prende comunque 0/100 a causa di output errati.

Qual è il problema di fondo?

Assicurati di controllare gli accessi agli iteratori, in particolare in queste due posizioni:

Come puoi vedere, le guardie del while accedono al valore di vb.rbegin() senza prima accertarsi che esista davvero il valore: puoi osservare che ad un certo punto l’iteratore punterà all’elemento finale della variabile – che è situato fuori dai margini della memoria. In poche parole, devi controllare che non stai accedendo a una boundary della struttura dati (indicata dall’iteratore std::multiset::end()).

Come fare per risolvere il problema?

Controlla in entrambe le guardie del while che non stia provando ad accedere a una boundary della struttura dati.

N.B. Se non dovesse compilare a causa di un no match for ‘operator!=’ (operand types are ‘std::multiset<long long int, std::greater<long long int> >::reverse_iterator’ and ‘std::multiset<long long int, std::greater<long long int> >::iterator’, assicurati che tu stia usando i puntatori giusti: in particolare std::multiset::rend() rappresenta il termine della struttura quando si itera al contrario.

Soluzione:

do {
    /*
     * la tua logica qui
     */
} while (vb.rbegin() != vb.rend() && /* le tue condizioni qui qui */);

Spero di essere stato d’aiuto, buona giornata! :slight_smile: