Pagini recente » Cod sursa (job #494756) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1534876) | Cod sursa (job #1034784)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <fstream>
using namespace std;
#define MAX_LEVEL 59
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;
}