Wheel of fortune problema

Ciao, sto cercando di svolgere wheel of fortune e sono convinto che per fare 100/100(fino ad ora ho fatto solo 70), devo segnare in una struct i valori del massimo e del minimo per ogni combinazione della ruota. Calcolando il minimo e il massimo con dei cicli for che vanno rispettivamente da 0 a n-1 e da n a 2n l ultimo subtask fallisce per il tempo.
ho deciso quindi di creare una deque e due multi set dove inserisco rispettivamente i valori che ci sono all interno nella ruota dopo gli spostamenti, i valori della prima metà e i valori della seconda meta.
Questo è il codice che ho creato ma per qualche motivo crasha e non riesco a capirlo:

#include<fstream>
#include<deque>
#include<set>
using namespace std;
int const MAXN=80000;
deque <int> A;
multiset<int> basso;
multiset<int> alto;
multiset<int>::iterator it;
multiset <int>::iterator ot;
struct minmax
{
    int mass;
    int mini;
}B[MAXN];

int main()
{
    ifstream in("input.txt");
    ofstream out("output.txt");
    int n;
    in>>n;
    int totali=2*n;
    int tmp;
    for(int i=0;i<totali;i++)
    {
        in>>tmp;
        A.push_back(tmp);
    }
    for(int i=0;i<n;i++)
    	basso.insert(A[i]);
    for(int i=n;i<totali;i++)
    	alto.insert(A[i]);
    
    for(int i=0;i<totali;i++)
    {
		B[i].mass=*alto.end();
		B[i].mini=*basso.begin();
		int ultimo=*A.end();
		int primo=A[n-1];
		it=alto.find(ultimo);
		ot=basso.find(primo);
		alto.erase(it);
		alto.insert(primo);
		basso.erase(ot);
		basso.insert(ultimo);
		tmp=*A.end();
		A.pop_back();
		A.push_front(tmp);
    }
    int m;
    in>>m;
    int indice;
    int posizione;
    for(int i=0;i<m;i++)
    {
        in>>indice;
        posizione+=indice;
        posizione=posizione%totali;
        out<<B[posizione].mini<<" "<<B[posizione].mass<<endl;
    }
}

Dove è l errore?

L’idea dovrebbe essere buona, anche se sicuramente si può fare di meglio credo che sia sufficiente.
Però sarebbe meglio se il codice lo postassi tramite pastebin o almeno come testo preformattato direttamente dal forum :slight_smile:

1 Mi Piace

Scusa come fai a fare meglio, con che strutture/algoritmo riesci a velocizzarlo?

Lì dovrebbe esserci tutto, comunque lo avevano chiesto anche qui :wink:

Non capisco perche se provo il secondo caso d esermpio su un compilatore me lo da giusto ma se lo sottopongo me lo da sbagliato, e comunque gli ultimi sforano il tempo lo stesso.

#include<fstream>
#include<set>
#include<deque>
using namespace std;
const int MAXN=80000;  
deque <int> primi;
deque <int> ultimi;
multiset<int> minimo;
multiset <int> massimo;
multiset<int>::iterator it;
struct valori
{
    int mini;
    int mass;
}tutti[MAXN];
int main()
{
    ifstream in("input.txt");
    ofstream out("output.txt");
    int n;
    in>>n;
    int totali=2*n;
    int tmp;
    for(int i=0;i<n;i++)
    {
        in>>tmp;
        primi.push_back(tmp);
        minimo.insert(tmp);
    }
    for(int i=0;i<n;i++)
    {
        in>>tmp;
        ultimi.push_back(tmp);
        massimo.insert(tmp);
    }
    for(int i=0;i<totali;i++)
    {
        tutti[i].mini=*minimo.begin();
        int cont;
        for(it=massimo.begin(); it!=massimo.end(); ++it)
            tutti[i].mass=*it;
        int valore=primi.back();
        primi.pop_back();
        minimo.erase(minimo.find(valore));
        ultimi.push_front(valore);
        massimo.insert(valore);
       
        int valore1=ultimi.back();
        ultimi.pop_back();
        massimo.erase(massimo.find(valore1));
        primi.push_front(valore1);
        minimo.insert(valore1);
    }
   
        int m;
    in>>m;
    int indice;
    int posizione;
    for(int i=0;i<m;i++)
    {
        in>>indice;
        posizione+=indice;
        posizione=posizione%totali;
        out<<tutti[posizione].mini<<" "<<tutti[posizione].mass<<endl;
    }
 
}

Nel penultimo ciclo for(dove calcoli i minimi e i massimi) usi un for per scorrere tutto il multiset sovrascrivendo ogni volta il valore che incontri, allo scopo di ottenere in tutti[i].mass l’ultimo elemento di massimo (e quindi il maggiore), tuttavia è sufficiente sostituire il for (che aumenta la complessità) con la riga
tutti[i].mass = *massimo.rbegin()
in modo da ottenere direttamente il puntatore all’ultimo elemento usando un reverse_iterator.

Non è per essere scortese ma ci aiuta molto poco se posti il codice con uno screenshot (anche se c’è in alto il link al pastebin) o se fai semplicemente copia incolla :slight_smile:
Comunque come diceva @gullpet per trovare l’ultimo elemento del multiset puoi utilizzare rbegin() o anche end() - 1

ok, ho messo la rbegin() e adesso il tempo non sfora il limite, mi crea comunque un problema perche se lo provo su un compilatore i risultati del secondo caso d’esempio sono giusti ma quando lo sottopongo non me li da corretti, dove potrebbe essere il problema?.
(Non capisco come usare pastebin in quanto mi crea un file .txt che non posso caricare qua sul forum)

Pastebin carica quel txt nel suo server e poi ti basta copiare qui il link :slight_smile:

Non saprei, potrebbe anche essere che gli esempi siano diversi ma di solito sono quelli per i problemi delle OIS.
Comunque ti potrebbe essere utile inventarti qualche caso d’esempio (o magari generarli in maniera casuale) e confrontare gli output del tuo programma con quelli di una versione meno efficiente che però sai funzionare correttamente per i primi testcase

Questo è il testo http://pastebin.com/9G8hEV8V
Il problema persiste, ho provato con un programma che mi da 70/100 per il tempo ma fa gli output giusti, in entrambi inserivo dati inventati da me e mi davano lo stesso risultato, non so cosa potrebbe esserci di sbagliato soprattutto perche(come avevo gia detto) il secondo esempio sul compilatore (dev) mi da il risultato giusto ma se lo provo mi dice che l output è sbagliato

Provando a eseguire con valgrind il tuo programma ottengo queste informazioni:

/tmp ❯❯❯ valgrind ./a.out
==30853== Memcheck, a memory error detector
==30853== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==30853== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==30853== Command: ./a.out
==30853== 
2
2 1 5 3
3
1 2 1
==30853== Use of uninitialised value of size 8
==30853==    at 0x400F8F: main (asd.cpp:62)
==30853== 
==30853== Use of uninitialised value of size 8
==30853==    at 0x400F9B: main (asd.cpp:62)
==30853== 
2 5
1 3
1 5
==30853== 
==30853== HEAP SUMMARY:
==30853==     in use at exit: 0 bytes in 0 blocks
==30853==   total heap usage: 21 allocs, 21 frees, 77,408 bytes allocated
==30853== 
==30853== All heap blocks were freed -- no leaks are possible
==30853== 
==30853== For counts of detected and suppressed errors, rerun with: -v
==30853== Use --track-origins=yes to see where uninitialised values come from
==30853== ERROR SUMMARY: 6 errors from 2 contexts (suppressed: 0 from 0)

Dice che alla riga 62 viene usata una variabile non inizializzata. L’output è corretto (è il primo caso d’esempio) ma è solo una coincidenza; in generale, usare una variabile non inizializzata è undefined behavior.

Ma se setto tutta la struct da 0 a totali (che sarebbe 2*n) e poi faccio l out di della struct ad un indice che è il risultato di un modulo totali (quindi sicuramente minore di totali) perché mi dice che non è inizializzata?

Devi inizializzare la variabile posizione (riga 56 :slight_smile:)

Grazie mille finalmente ho fatto 100, credo di essere il primo di tutta la piattaforma a fare 92 sottoposizioni per lo stesso problema prima di fare 100