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;
}