All pastes #487633 Raw Edit

Unnamed

public text v1 · immutable
·published 2007-05-14 15:47 UTC
rendered paste body
#include <stdio.h>
#include <stdlib.h>

typedef unsigned int uint;


/* = hash = */

typedef struct {
	int key;
	uint value;
} ht_entry_t;

typedef struct {
	uint mask;
	uint fill;
	uint thres;
	ht_entry_t *table;
} ht_t;

static inline ht_t *ht_alloc();
static inline ht_t *ht_init(ht_t *ht);
static inline ht_t *ht_free(ht_t *ht);
static inline ht_t *ht_uninit(ht_t *ht);
static inline ht_entry_t *ht_lookup(ht_t *ht, int key);
static inline void ht_inc(ht_t *ht, int key);
static inline uint ht_get(ht_t *ht, int key);
static inline ht_t *ht_resize(ht_t *ht, uint hint);

#define NDEBUG
#include <assert.h>

#define hash(x) x

#define HT_MINSIZE 8
#define HT_MAXSIZE 1<<29

#define JUMP(i, j) i += j++
#define JUMP_FIRST(i, j) j = 1, i += j++

static inline void HT_CHECKFILL(ht_t *ht)
{
	if (ht->fill >= ht->thres) {
		ht_resize(ht, ht->fill << 2);
	}
}

static inline ht_t *ht_alloc()
{
	ht_t *ht = malloc(sizeof(ht_t));
	assert(ht);
	return ht_init(ht);
}

static inline ht_t *ht_init(ht_t *ht)
{
	ht->mask = 8 - 1;
	ht->thres = ((ht->mask + 1) * 3) >> 2;
	ht->fill = 0;
	ht->table = calloc(ht->mask + 1, sizeof(ht_entry_t));
	assert(ht->table);
	return ht;
}

static inline ht_t *ht_uninit(ht_t *ht)
{
	ht_entry_t *table = ht->table;
	ht->table = NULL;
	free(table);
	return ht;
}

static inline ht_t *ht_free(ht_t *ht)
{
	ht_uninit(ht);
	free(ht);
	return NULL;
}

static inline ht_entry_t *ht_lookup(ht_t *ht, int key)
{
	uint mask = ht->mask;
	uint i = hash(key);
	uint j; /* JUMP_QUAD, JUMP_PY */
	ht_entry_t *table = ht->table;
	ht_entry_t *entry = table + (i & mask);
	assert(ht->table != NULL);
	if (entry->value == 0 || entry->key == key) {
		return entry;
	}
	assert(ht->fill <= ht->mask);
	for (JUMP_FIRST(i, j); ; JUMP(i, j)) {
		entry = table + (i & mask);
		if (entry->value == 0 || entry->key == key) {
			return entry;
		}
	}
}

static inline void ht_cleaninsert(ht_t *ht, int key, uint value)
{
	uint mask = ht->mask;
	uint i = hash(key);
	uint j;
	ht_entry_t *table = ht->table;
	ht_entry_t *entry = table + (i & mask);
	if (entry->value) {
		for (JUMP_FIRST(i, j); entry->value; JUMP(i, j)) {
			entry = table + (i & mask);
		}
	}
	++ht->fill;
	entry->key = key;
	entry->value = value;
}

static inline ht_t *ht_resize(ht_t *ht, uint hint)
{
	uint newsize;
	uint oldfill = ht->fill;
	ht_entry_t *oldtable, *newtable, *entry;
	if (hint < oldfill << 1) {
		hint = oldfill << 1;
	}
	for (newsize = HT_MINSIZE; newsize < hint || newsize <= oldfill; newsize <<= 1) {
		assert(newsize < HT_MAXSIZE);
	}
	newtable = calloc(newsize, sizeof(ht_entry_t));
	assert(newtable != NULL);
	oldtable = ht->table;
	ht->table = newtable;
	ht->mask = newsize-1;
	ht->thres = (3 * newsize) >> 2;
	ht->fill = 0;
	for (entry = oldtable; oldfill; ++entry) {
		if (entry->value) {
			--oldfill;
			ht_cleaninsert(ht, entry->key, entry->value);
		}
	}
	free(oldtable);
	return ht;
}

static inline uint ht_get(ht_t *ht, int key)
{
	ht_entry_t *entry = ht_lookup(ht, key);
	return entry->value;
}

static inline void ht_inc(ht_t *ht, int key)
{
	ht_entry_t *entry = ht_lookup(ht, key);
	if (entry->value) {
		++entry->value;
	} else {
		++ht->fill;
		entry->key = key;
		entry->value = 1;
		HT_CHECKFILL(ht);
	}
}


/* = sumfour = */

int *A;
int *B;
int *C;
int *D;
uint n;

void readin()
{
	char s[60];
	char *p;
	uint i;
	
	fgets(s, 60, stdin);
	n = atoi(s);
	
	A = malloc(4 * n * sizeof(int));
	B = A + n;
	C = B + n;
	D = C + n;
	
	for (i = 0; i < n; ++i) {
		fgets(s, 60, stdin);
		A[i] = strtol(s, &p, 10);
		B[i] = strtol(p, &p, 10);
		C[i] = strtol(p, &p, 10);
		D[i] = strtol(p, &p, 10);
	}
}

uint count()
{
	uint i;
	uint j;
	uint s = 0;
	ht_t *ht;
	int a, c;
	
	ht = ht_resize(ht_alloc(), 6*n);
	i = n;
	while (i) {
		a = A[--i];
		j = n;
		while (j) {
			ht_inc(ht, a + B[--j]);
		}
	}
	i = n;
	while (i) {
		c = -C[--i];
		j = n;
		while (j) {
			s += ht_get(ht, c - D[--j]);
		}
	}
//	ht_free(ht);
	return s;
}

int main()
{
	readin();
	printf("%u\n", count());
//	free(A);
	return 0;
}