Ciao a tutti, chi mi sa dare un aiuto per risolvere l'ultimo subtask del problema ZigZag? Il mio codice è:
#include <fstream> #include <cstdlib> #include <algorithm> #define MAXN 100001
using namespace std;
ifstream fin ("input.txt"); ofstream fout("output.txt"); int N; int sequenza[MAXN],soluzioni[MAXN][2]; int massimo,temp;
int main() { fin>>N; for(int i=0;i<N;i++) { fin>>sequenza[i]; //soluzioni[i][0]=soluzioni[i][1]=1; } for(int i=0;i<N-1;i++) for(int j=i+1;j<N;j++) { temp=sequenza[i]-sequenza[j]; if(temp>0 && soluzioni[i][1]+1>soluzioni[j][0]) soluzioni[j][0]=soluzioni[i][1]+1; else if(temp<0 && soluzioni[i][0]+1>soluzioni[j][1]) soluzioni[j][1]=soluzioni[i][0]+1; } for(int i=0;i<N;i++) { if(soluzioni[i][0]>massimo) massimo=soluzioni[i][0]; if(soluzioni[i][1]>massimo) massimo=soluzioni[i][1]; } fout<<massimo+1; }
Praticamente lo risolvo utilizzando la programmazione dinamica: nel vettore sequenza tengo la sequenza di numeri, nella matrice soluzioni tengo le soluzioni nel caso in cui la somma sia positiva (colonna 0) o negativa (colonna 1). Alla fine ricerco il massimo e lo stampo. La soluzione è corretta, ma con l'ultimo subtask vado fuori tempo limite. Come posso risolvere?
Gaspare mica ti vieni a fare un giro alle OII sto anno? Mi piacerebbe conoscerti: fra te e Milizia (di cui conosco solo le leggende -) non so a chi fare la statua :0 Siete irraggiungibili ç__ç
Coooomunque io con la Greedy lo faccio in 0.01, che cavolo mi manca per farlo in 0 :0
Non c’è motivo di credere che il C++ sia in generale più lento del C.
La cosa che prende gran parte del tempo (nei problemi in cui va fatto) è spesso l’I/O (anche per questo motivo si sta passando ai grader).
Per fare 0.00s in genere basta scrivere una funzione che legge/scrive interi velocemente (ad esempio, leggendo carattere per carattere con getchar_unlocked()).
Chiedo venia, ma mi pare che l’I/O del C fosse più veloce di quello del C++, ma forse ricordo male (o comunque, a quanto pare, ho erroneamente esteso il discorso ad ogni parte dei due linguaggi).
Gaspare non ci siamo conosciuti l’anno scorso, io sono Roberto Stagi (scontentissimo per i miei 15 punti dell’anno scorso, pronto per riscattarmi quest’anno).
Per Gaspare in particolare, ma per chiunque abbia una risposta :) Con questo codice faccio giusti i primi 4 subtask in 0.000 secondi, ma per l'ultimo mi da output non corretto... mi sfugge qualcosa? Grazie!
// array con i numeri letti int array[n];
// array con le differenze (l'elemento diff[i] contiene 1 se array[i]-array[i+1] > 0; -1 altrimenti) int diff[n-1]; for(i=0; i<n-1; i++) if(array[i]-array[i+1] > 0) diff[i] = 1; else diff[i] = -1;
int count; int last; // count è la lunghezza sequenza count = 1;
// last vale 1 se l'ultima differenza era positiva; -1 altrimenti last = 1;
// per ogni differenza, se è diversa dall'ultima incremento la lunghezza della stringa e aggiorno il segno dell'ultima differenza (last) for(i=0; i<n-1; i++) if(diff[i] != last){ last = diff[i]; count++; } int max = count; // ripeto tutto, ma partendo con il segno della prima differenza diverso da quello di prima count = 1; last = -1;
for(i=0; i<n-1; i++) if(diff[i] != last){ last = diff[i]; count++; } // aggiorno max se necessario if(count > max) max = count; // stampo max su file
Devi anche considerare il caso in cui ci siano due elementi consecutivi uguali! Ad esempio, con l’input {5, 5, 4, 4, 3, 3} il tuo programma restituisce 6 (in quanto considera la differenza tra due numeri uguali negativa), mentre il risultato corretto è 2!
anche se ero scontento perchè ho perso l’oro per un banalissimo