#include <limits.h>
#include <pthread.h>
#include "suma.h"
// Defina aca las estructuras que necesite
enum {NTHREADS= 8};
typedef long long ll;
typedef struct {
  int *a;
  ll *prefix;
  int n;
  Set inicio;
  Set fin;
  Set encontrado;
} ArgsBuscar;
static Set total_combinaciones(int n) {
  if (n >= (int)(sizeof(Set) *CHAR_BIT))
    return ~(Set)0;
  return ((Set)1 << n)-1;
}
static ll suma_subconjunto(int a[], int n, Set k) {
  ll suma=0;
  for (int i=0; i<n;i++) {
    if (k & ((Set)1 << i))
      suma +=a[i];
  }
  return suma;
}
static int contar_unos_finales(Set k) {
  int cant=0;
  while ((k&1)!=0) {
    cant++;
    k >>= 1;
  }
  return cant;
}
static Set buscar_rango(int a[], ll prefix[], int n, Set inicio, Set fin) {
  if (inicio == 0 || inicio > fin)
    return 0;
  Set k = inicio;
  ll suma = suma_subconjunto(a, n, k);
  while (1) {
    if (suma == 0)
      return k;
    if (k == fin)
      break;
    int cambios = contar_unos_finales(k);
    suma -= prefix[cambios];
    suma += a[cambios];
    k++;
  }
  return 0;
}
// Defina aca la funcion que ejecutaran los threads
static void *thread_buscar(void *ptr) {
  ArgsBuscar *args = ptr;
  args->encontrado = buscar_rango(args->a, args->prefix, args->n, args->inicio,
                                  args->fin);
  return NULL;
}
// Reprograme aca la funcion buscar
Set buscar(int a[],int n) {
  Set comb= total_combinaciones(n);
  Set base= comb / NTHREADS;
  Set extra =comb % NTHREADS;
  Set siguiente =1;
  pthread_t tids[NTHREADS];
  ArgsBuscar args[NTHREADS];
  ll prefix[CHAR_BIT * sizeof(Set) + 1];
  int creados = 0;
  prefix[0] = 0;
  for (int i = 0; i < n; i++)
    prefix[i + 1] = prefix[i] + a[i];
  for (int t = 0; t < NTHREADS; t++) {
    Set largo = base + (Set)(t < (int)extra);
    args[t].a = a;
    args[t].prefix = prefix;
    args[t].n = n;
    args[t].inicio = siguiente;
    args[t].fin = (largo == 0) ? siguiente - 1 : siguiente + largo - 1;
    args[t].encontrado = 0;
    if (largo != 0)
      siguiente =args[t].fin + 1;
    if (pthread_create(&tids[t], NULL, thread_buscar, &args[t]) != 0) {
      for (int i = 0; i < creados; i++)
        pthread_join(tids[i], NULL);
      return buscar_rango(a, prefix, n, 1, comb);
    }
    creados++;
  }
  Set mejor=0;
  for (int t=0; t<NTHREADS;t++) {
    pthread_join(tids[t], NULL);
    if (args[t].encontrado != 0 &&
        (mejor == 0||args[t].encontrado<mejor))
      mejor=args[t].encontrado;
  }
  return mejor;
}