Cod sursa(job #1514831)

Utilizator stoianmihailStoian Mihail stoianmihail Data 31 octombrie 2015 17:42:52
Problema Lupul Urias si Rau Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <stdio.h>
#include <stdlib.h>

#define aibSize 131072
#define Nadejde 100000
#define NIL -1

typedef struct {
  int v, time;
} cell;

typedef struct {
  int v, next;
} list;

typedef struct {
  int v, pos;
} order;

int *adj, inside;
int N, L, X, buff;
cell save[Nadejde];        // vectorul de la intrare modificat.
list l[Nadejde + 1];       // lista cu lana oilor.
int aib[aibSize + 1];      // structura heap.
order sorted[Nadejde + 1]; // normalizam listele cu lana oilor.

/** Aloca-mi un vector de "size" + 1 elemente. **/
void alloc(int size) {
  adj = (int*)calloc(size + 1, sizeof(int));
}

/** Adauga la lista "pos" valoarea "val". **/
void add(int pos, int val) {
  l[++buff].v = val;
  l[buff].next = adj[pos];
  adj[pos] = buff;
}

/** Sorteaza crescator structura "sorted". **/
void sort(int begin, int end) {
  int b = begin, e = end, pivot = sorted[(b + e) >> 1].v;
  while (b <= e) {
    while (sorted[b].v < pivot) {
      b++;
    }
    while (sorted[e].v > pivot) {
      e--;
    }
    if (b <= e) {
      order tmp = sorted[b];
      sorted[b++] = sorted[e];
      sorted[e--] = tmp;
    }
  }
  if (begin < e) {
    sort(begin, e);
  }
  if (b < end) {
    sort(b, end);
  }
}

/** Normalizeaza lista. **/
void normalize(int size) {
  int i;
  for (i = 1; i <= size; i++) {
    l[sorted[i].pos].v = i;
  }
}

/** Insereaza in aib pozitia "x" cu valoarea "val". **/
void insert(int x, int val) {
  do {
    aib[x] += val;
    x += x & -x;
  } while (x <= aibSize);
  inside += val;
}

/** Cauta binar valoarea "val" in aib. **/
int search(int val) {
  int x = 0, interval;
  for (interval = aibSize >> 1; interval; interval >>= 1) {
    if (aib[x + interval] < val) {
      val -= aib[x += interval];
    }
  }
  return x + 1;
}

/** Da-mi cel mai mare numar disponibil din aib. **/
int maxHeap() {
  int pos = search(inside);
  insert(pos, NIL);
  return sorted[pos].v;
}

int main(void) {
  long long int sum = 0;
  int i, val, pos, dist, max = 0, size = 0;
  FILE *f = fopen("lupu.in", "r");

  /* Citeste caracteristicile oilor. **/
  fscanf(f, "%d %d %d", &N, &X, &L);
  for (i = 0; i < N; i++) {
    fscanf(f, "%d %d", &dist, &save[i].v);
    if (dist <= X) {
      save[i].time = (X - dist) / L + 1;
      if (save[i].time > max) {
        max = save[i].time;
      }
    }
  }
  fclose(f);

  f = fopen("lupu.out", "w");

  alloc(max);

  /* Adauga in lista structura "save". */
  for (i = 0; i < N; i++) {
    if (save[i].time) {
      add(save[i].time, save[i].v);
      sorted[++size].v = save[i].v;
      sorted[size].pos = buff;
    }
  }

  /* Normalizeaza "sorted". */
  sort(1, size);
  normalize(size);

  /* Calculeaza cantitatea maxima de lana pe care o poate obtine lupul. */
  for (i = max; i > 0; i--) {
    for (pos = adj[i]; pos; pos = l[pos].next) {
      insert(l[pos].v, -NIL);
    }
    if (inside) {
      sum += maxHeap();
    }
  }
  fprintf(f, "%lld\n", sum);
  fclose(f);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}