Cod sursa(job #1435672)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 14 mai 2015 00:50:39
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>
#include <string.h>

#define MAX_C 1024
#define MOD 666013
#define NIL -1
#define f(x) ((x) - (x) / MOD * MOD)

typedef struct {
  int key, next;
  int minIndc;
} cell;

cell l[MAX_C * (MAX_C - 1) / 2];   // buffer prealocat
int buffPtr;                       // prima pozitie libera in buffer
int h[MOD];                        // capat de liste alocate static
int a[MAX_C];                      // vector de cantitati de blana

void hashInsert(int key, int i, int j) {
  l[buffPtr].key = key;
  l[buffPtr].minIndc = (i < j) ? i : j;
  l[buffPtr].next = h[f(key)];
  h[f(key)] = buffPtr;
  buffPtr++;
}
inline int countKey(int key, int x, int y) {
  if (key < 0) {
    return 0;
  }
  int ans = 0;
  int chk = (x > y ? x : y);

  for (int i = h[f(key)]; i != NIL; i = l[i].next) {
    ans = ans + (l[i].key == key && l[i].minIndc > chk);
  }
  return ans;
}
int main(void) {
  FILE *f = fopen("oite.in", "r");
  int c, sum;

  for (int i = 0; i < MOD; i++) {
    h[i] = NIL;
  }

  fscanf(f, "%d%d", &c, &sum);
  for (int i = 0; i < c; i++) {
    fscanf(f, "%d", &a[i]);
  }
  fclose(f);

  for (int i = 0; i < (c - 1); i++) {
    for (int j = i + 1; j < c; j++) {
      hashInsert(a[i] + a[j], i, j);
    }
  }
  int cnt = 0;
  for (int i = 0; i < (c - 1); i++) {
    for (int j = i + 1; j < c; j++) {
      cnt = cnt + countKey(sum - a[i] - a[j], i, j);
    }
  }
  f = fopen("oite.out", "w");
  fprintf(f, "%d\n", cnt);
  fclose(f);
  return 0;
}