Cod sursa(job #1513231)

Utilizator stoianmihailStoian Mihail stoianmihail Data 29 octombrie 2015 09:39:02
Problema Lupul Urias si Rau Scor 44
Compilator c Status done
Runda Arhiva de probleme Marime 3.45 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_VALUE 2147483648
#define MAX_RAND 524287
#define MAX_SIZE 300000
#define Nadejde 100000
#define MAX_LEVEL 20

typedef struct {
  int v, time;
} cell;

typedef struct {
  int v, next;
} list;

int *adj, inside;
int level, bufPtr;
int N, L, X, buff;
cell save[Nadejde];        // vectorul de intrare modificat.
list l[Nadejde + 1];       // lista cu lana oilor.
int update[MAX_LEVEL];     // folosit in timpul inserarii.
unsigned int sl[MAX_SIZE]; // zona de memorie prealocata.

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

/** Initializeaza structura. **/
void init() {
  sl[0] = -MAX_VALUE;
  sl[MAX_LEVEL + 1] = MAX_VALUE;

  int l;
  for (l = 1; l <= MAX_LEVEL; l++) {
    sl[l] = MAX_LEVEL + 1;
  }
  level = 1;
  bufPtr = MAX_LEVEL + 2;
}

/** Da-mi un nivel random. **/
int randomLevel() {
  int r, l = 0;
  for (r = rand() & MAX_RAND; r; r >>= 1) {
    l++;
  }
  return l;
}

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

/** Insereaza in structura valoarea "x". **/
void insert(int x) {
  int l, pos = 0;
  for (l = level - 1; l >= 0; l--) {
    while (sl[sl[pos + l + 1]] < x) {
      pos = sl[pos + l + 1];
    }
    update[l] = pos;
  }

  int newLevel = randomLevel();
  if (newLevel > level) {
    for (l = level; l < newLevel; l++) {
      update[l] = 0;
    }
    level = newLevel;
  }

  sl[bufPtr] = x;
  for (l = 0; l < newLevel; l++) {
    sl[bufPtr + l + 1] = sl[update[l] + l + 1];
    sl[update[l] + l + 1] = bufPtr;
  }
  bufPtr += newLevel + 1;
  inside++;
}

/** Sterge din structura valoarea "x". **/
void erase(int x) {
  int l, pos = 0;
  for (l = level - 1; l >= 0; l--) {
    while (sl[sl[pos + l + 1]] < x) {
      pos = sl[pos + l + 1];
    }
    update[l] = pos;
  }
  pos = sl[pos + 1];

  l = 0;
  while ((l < level) && (sl[update[l] + l + 1] == pos)) {
    sl[update[l] + l + 1] = sl[pos + l + 1];
    l++;
  }
  inside--;
}

/** Da-mi elementul maxim din structura. **/
int maxHeap() {
  int l, val, pos = 0;
  for (l = level - 1; l >= 0; l--) {
    while (sl[sl[pos + l + 1]] < MAX_VALUE) {
      pos = sl[pos + l + 1];
    }
  }
  val = sl[pos];
  erase(val);
  return val;
}

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

  init();

  /* 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);
    }
  }

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

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