Cod sursa(job #1034783)

Utilizator cosminpdrfischer2004 cosminp Data 18 noiembrie 2013 03:54:29
Problema Dtcsu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <fstream>

using namespace std;

#define MAX_LEVEL 60

typedef struct NODE
{
	NODE *left;
	NODE *right;
}NODE;


NODE* GetNewNode()
{
	NODE *node = (NODE*)malloc(sizeof(NODE));
	node->left = node->right = NULL;
	return node;
}

void AddValue(NODE *node, int level, long long x)
{
	if (level == MAX_LEVEL) return;

	if (x & 1)
	{
		// allocate the node if it doesn't exist
		if (node->right == NULL) node->right = GetNewNode();
		AddValue(node->right, level + 1, x >> 1);
	}
	else
	{
		// allocate the node if it doesn't exist
		if (node->left == NULL) node->left = GetNewNode();
		AddValue(node->left, level + 1, x >> 1);
	}
}


bool IsValueStored(NODE *node, int level, long long x)
{
	if (node == NULL) return (level == (MAX_LEVEL + 1));
	return IsValueStored((x & 1) ? node->right : node->left, level + 1, x >> 1);
}


void DestroyTree(NODE *node)
{
	if (node == NULL) return;

	DestroyTree(node->left);
	DestroyTree(node->right);
	free(node);
}


int main()
{
	fstream 	f, g;
	int 		q, count = 0;
	long long 	x;
	NODE 		*trie = GetNewNode();

	f.open("dtcsu.in", ios :: in);
	for (int i = 0; i < 276997; i++)
	{
		f >> x;
		AddValue(trie, 0, x);
	}

	f >> q;
	for (int i = 0; i < q; i++)
	{
		f >> x;
		if (IsValueStored(trie, 0, x)) count++;
	}
	f.close();

	g.open("dtcsu.out", ios :: out);
	g << count;
	g.close();

	DestroyTree(trie);

	return 0;
}