Stavo provando a risolvere il problema, credo di aver trovato un modo corretto per risolverlo ma ottengo 30/100, 3 Execution killed with signal 11 e il resto timeout.
Questo è il codice: http://pastebin.com/yFrujxBR
L’algoritmo è semplice, ho un array abbattuti[MAXN] con cui tengo conto degli alberi abbattuti, viene resettato ad ogni chiamata ad abbatti, lo pseudocodice è questo:
Trova il muro più vicino a X (e dipende da D)
Se non ce n’è ritorna D
Se non è già abbattuto, abbatti questo muro, inverti marcia e passa al muro precedente/successivo, ripeti quest’ultimo passaggio finché non rimangono più muri da un lato.
Temo che il tuo algoritmo non sia sufficiente per ottenere un punteggio pieno, dato che per ogni chiamata ad Abbatti potrebbe essere necessario considerare N muri.
Dovresti cercare di cosa fa variare il risultato dell’esecuzione piuttosto che simularla
Comunque il problema nel tuo codice è nell’assegnazione che fai al valore di muro all’inizio, perché se gli assegni 1<<30 e poi non incontri nessun muro minore di X andrai ad accedere a una posizione non valida nell’array abbattuti, con conseguente “Execution killed with signal 11”
Mi sa di errore nel codice, l’algoritmo dovrebbe essere giusto (anche se non credo che ottenga 100/100 ma vada ottimizzato ancora). Come decidi il risultato in base al numero di muri a destra e sinistra?
Se hai 8 muri alla tua destra, e 7 alla tua sinistra, indipendentemente dalla tua direzione uscirai sempre a destra. E viceversa. La direzione conta in un caso speciale (e penso sia stato chiaro).
C’è già una funzione di libreria STL che fa quello che cerchi, ma non te la dico per fartela cercare, nel caso tu non la conosca.
Un’ultima cosa: rischi un buffer overflow con la memset, perché abbattuti è un vettore di int, quindi la memoria occupata da memset è di MAXN*4 (in molte macchine ha dimensione di 4 byte).
L’algoritmo, seppure ancora non abbastanza veloce, sembra corretto; però per renderlo sufficientemente veloce devi per lo meno trovare un modo più rapido per contare quanti muri precedono la posizione della ruspa.
Per quanto riguarda il codice invece, c’è un bel po’ di confusione
Se hai detto che vuoi solo sapere quanti muri ci sono prima e quanti dopo, perché non conti semplicemente i muri minori di X con un ciclo?
In realtà non serve nessuna funzione, se consideri il fatto che non ti interessa davvero sapere quanti ne hai destra e quanti a sinistra
Probabilmente hai ragione. Io ho comunque risolto così, ovvero facendo un confronto tra numero di quelli che stanno dietro e quelli che stanno davanti. Per farlo ho usato la upper_bound, ma niente toglie di farsela da sè (è comoda perché fa pure ricerca binaria, ma lo so si può vivere anche senza)
