#define USECHRONO
#undef HAVE_MPI

#include "eval.hpp"
#include <cassert>
#include <climits>
#include <cstdlib>
#include <stack>
using namespace aed;
using namespace std;


//---:---<*>---:---<*>- COMIENZA CODIGO FUNCION --:---<*>---:---<*>---:---<*>
// COMPLETAR DNI y NOMBRE AQUI:
// Nombre: Lucas Velazquez
int DNI=42581665;

/// Función de diferencia entre conjuntos que habiamos hecho en clase, por las dudas.
void set_difference(set<int> &A, set<int> &B, set<int> &C) {
  C.clear();
  set<int>::iterator itA = A.begin(), itB = B.begin();
  while(itA != A.end() && itB != B.end()){
    if (*itA == *itB) {
      itA++; itB++;
    }
    else if (*itA < *itB){
      C.insert(*itA);
      itA++;
    }
    else {
      itB++;
    }
  }
  while (itA != A.end()){
    C.insert(C.end(), *itA);
    ++itA;
  }
}

/// Devuelve el promedio del conjunto.
double promedio_set(set<int> &S){
  double prom = 0;
  for(auto e : S) prom += e;
  return prom / S.size();
}

/// Devuelve todos los subconjuntos propios del conjunto S.
void subset_prop(set<int> &S, set<int> C, set<int>::iterator itS, list<set<int>> &LK) {
  if (itS == S.end()) return;
  set<int> D = C;
  
  C.insert(*itS);
  itS++;
  if(C.size() != S.size()) LK.push_back(C);
  
  subset_prop(S,C,itS,LK);
  subset_prop(S,D,itS,LK);
}

list<set<int>> subset_prop(set<int> &S) {	
  set<int> C;
  list<set<int>> LK;
  subset_prop(S,C,S.begin(),LK);	
  return LK;	
}

/// Devuelve si A < B
bool rel_orden_menor(set<int> A, set<int> B){
  if(!A.empty() && B.empty()) return false;
  if(A.empty() && !B.empty()) return true;
  auto itA = max_element(A.begin(), A.end());
  auto itB = max_element(B.begin(), B.end());
  if(*itA < *itB) return true;
  
  set<int> tmpA, tmpB;
  set_difference(A, {*itA}, tmpA);
  set_difference(B, {*itB}, tmpB);
  return rel_orden_menor(tmpA, tmpB);
}

void get_largest_subset(set<int> &S, set<int> &C){
  if(S.empty()) return; // Si está vacío devuelve el conjunto vacío.
  list<set<int>> LS;
  LS = subset_prop(S); // Hace una lista con todos los subconjuntos propios de S.
  double prom_S = promedio_set(S); // Saca el promedio de S.
  
  // prom_lsub es el promedio de C.
  // prom_tmp es el promedio del subconjunto auxiliar.
  double prom_tmp, prom_lsub = 0;
  for(auto e : LS){
    prom_tmp = promedio_set(e); // Calcula el promedio del set auxiliar.
    double dist_tmp = fabs(prom_tmp-prom_S); // Distancia entre tmp y S.
    double dist_lsub = fabs(prom_lsub-prom_S); // Distancia entre lsub y S.
    // Si la distancia entre tmp y S es menor que la distancia entre lsub y 
    // S.
    if(dist_tmp < dist_lsub){ 
      prom_lsub = prom_tmp;
      C = e;
    } // Si ambas distancias son iguales, desempata por relación de orden menor.
    else if(dist_tmp==dist_lsub && rel_orden_menor(C, e)){
        prom_lsub = prom_tmp;
        C = e;
    }
  }
}
//---:---<*>---:---<*>- FINALIZA CODIGO FUNCION --:---<*>---:---<*>---:---<*>
int main() {
  Eval ev;
  int vrbs=0;
  ev.eval<1>(get_largest_subset,vrbs);
  return 0;
}