Wheel aiuto TLE

Aiuto
1

Salve a tutti,
sto provando a risolvere il problema ois_wheel e fin’ora riesco ad ottenere soltanto 70/100,
il metodo che utilizzo è basato sulle strutture dati queue e multiset.
Infatti utilizzo due code (avrei potuto usare una deque) per memorizzare gli elementi presenti nelle due parti della ruota e due multiset che mi permettono velocemente di vedere il minimo-massimo di ogni insieme.
Non trovo altri modi per fare questo esercizio più velocemente…
Qualche suggerimento?

#include <fstream>
#include <set>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;

int main(){
	ifstream in("input.txt");
	ofstream out("output.txt");
	
	int n; 
	in >> n; 
	queue<int> codaMin;
	queue<int> codaMax;
	multiset<int> minimo;
	multiset<int> massimo;
	std::multiset<int>::iterator it;
	int v[n],v1[n];			
	for(int i=0; i<n; i++){		
		int a; 
		in >> a;
		minimo.insert(a);
		v[i] = a;
	}
	for(int i=0; i<n; i++){		
		int a; 
		in >> a;
		massimo.insert(a);
		v1[i] = a;
	}
	
	for(int i=n-1; i>=0; i--){
		codaMin.push(v[i]);
		codaMax.push(v1[i]);
	}
	
	int q ;
	in >> q;
	
	for(int i=0; i<q; i++){
		int k;
		in >> k; 
		k = k % (2*n);
		if(k >= n){
			k-=n;
			swap(minimo,massimo);
			swap(codaMin,codaMax);
		}
		
		for(int z=0; z<k; z++){
			int ext = codaMin.front();
			codaMin.pop();
			minimo.erase(minimo.find(ext));
			massimo.insert(ext);
			codaMax.push(ext);
			
			ext = codaMax.front();
			codaMax.pop();
			massimo.erase(massimo.find(ext));
			codaMin.push(ext);
			minimo.insert(ext);
		}
		
		for(std::multiset<int>::iterator it=minimo.begin(); it!=minimo.end(); ++it){
			out << *it << " ";
			break;
		}
		for(std::multiset<int>::iterator it=massimo.end(); it==massimo.end(); ++it){
			it--;
			out << *it <<endl;;
			break;
		}
		
	}
	
	
	return 0;
}
2

Non ti serve un ciclo per stampare minimo.begin() e massimo.end() :innocent:

Comunque se non ho capito male tu simuli la rotazione della ruota andando a modificare inserendo/rimuovendo ciascun elemento uno alla volta. Questo significa che potresti effettuare fino ad N inserimenti per andare in una posizione che magari avevi già calcolato nel simulare la rotazione precedente della ruota.

Diciamo che ti basta simulare soltanto una rotazione completa se memorizzi per ogni possibile stato della ruota quali sono i due valori che ti interessano :slight_smile:

3

Grazie mille per l’aiuto, ora funziona…
Per quanto riguarda il ciclo era lì per un “debug” e poi non l’ho tolto solo perché continuavo a testarlo avevo aggiunto semplicemente un break.