Cod sursa(job #1164356)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 2 aprilie 2014 00:01:19
Problema Hashuri Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.02 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
 
#define MOD 7
#define BIT(x , nr) ((x & (1<<nr)) != 0) 
 
vector <int> v[8][8][8][8][8][8];
int maxim;

inline void hash(int val, int &a, int &b, int &d, int &x, int &y, int &z)
{
	a=BIT(val,0)+2*BIT(val,2)+4*BIT(val,4);
	b=BIT(val,7)+2*BIT(val,8)+4*BIT(val,10);
	d=BIT(val,12)+2*BIT(val,14)+4*BIT(val,15);
	x=BIT(val,16)+2*BIT(val,17)+4*BIT(val,18);
	y=BIT(val,21)+2*BIT(val,22)+4*BIT(val,24);
	z=BIT(val,28)+2*BIT(val,29)+4*BIT(val,30);
}
	
inline int cauta(int val)
{
    int i,n,a,b,d,x,y,z;
	hash(val,a,b,d,x,y,z);
	n=v[a][b][d][x][y][z].size()-1;
	if(n>maxim)
		maxim=n;
    for(i=0;i<=n;i++)
        if(v[a][b][d][x][y][z][i]==val)
            return i;
	return -1;
}
 
inline void adauga(int val)
{
	int a,b,d,x,y,z;
    if(cauta(val)==-1) {
		hash(val,a,b,d,x,y,z);
		v[a][b][d][x][y][z].push_back(val);
	}
}
 
inline void sterge(int val)
{
    int poz,a,b,d,x,y,z;
    poz=cauta(val);
    if(poz!=-1) {
		hash(val,a,b,d,x,y,z);
		v[a][b][d][x][y][z].erase(v[a][b][d][x][y][z].begin()+poz);
	}
}
int main ()
{
    int n,i,op,x;
    ifstream f("hashuri.in");
    ofstream g("hashuri.out");
    f>>n;
    for(i=1;i<=n;i++) {
        f>>op>>x;
        if(op==1)
            adauga(x);
        else if(op==2)
            sterge(x);
        else {
            if(cauta(x)==-1)
                g<<"0"<<'\n';
            else g<<"1"<<'\n';
        }
    }
	cout<<maxim;
    f.close();
    g.close();
	return 0;
}

/*
#define hashsize(n) ( 1U << (n) )
#define hashmask(n) ( hashsize ( n ) - 1 )
  
#define mix(a,b,c) \
{ \
	a -= b; a -= c; a ^= ( c >> 13 ); \
    b -= c; b -= a; b ^= ( a << 8 ); \
	c -= a; c -= b; c ^= ( b >> 13 ); \
	a -= b; a -= c; a ^= ( c >> 12 ); \
	b -= c; b -= a; b ^= ( a << 16 ); \
	c -= a; c -= b; c ^= ( b >> 5 ); \
	a -= b; a -= c; a ^= ( c >> 3 ); \
	b -= c; b -= a; b ^= ( a << 10 ); \
	c -= a; c -= b; c ^= ( b >> 15 ); \
}

unsigned jen_hash ( unsigned char *k, unsigned length, unsigned initval ) {
	unsigned a, b;	
	unsigned c = initval;
	unsigned len = length;
	a = b = 0x9e3779b9;
	while ( len >= 12 ) {
		a += ( k[0] + ( (unsigned)k[1] << 8 ) + ( (unsigned)k[2] << 16 ) + ( (unsigned)k[3] << 24 ) );
		b += ( k[4] + ( (unsigned)k[5] << 8 ) + ( (unsigned)k[6] << 16 ) + ( (unsigned)k[7] << 24 ) );
		c += ( k[8] + ( (unsigned)k[9] << 8 ) + ( (unsigned)k[10] << 16 ) + ( (unsigned)k[11] << 24 ) );
		mix ( a, b, c );
		k += 12;	
		len -= 12;
    }
 
    c += length;
 
    switch ( len ) {
		case 11: c += ( (unsigned)k[10] << 24 );
		case 10: c += ( (unsigned)k[9] << 16 );
		case 9 : c += ( (unsigned)k[8] << 8 );
		case 8 : b += ( (unsigned)k[7] << 24 );
		case 7 : b += ( (unsigned)k[6] << 16 );
		case 6 : b += ( (unsigned)k[5] << 8 );
		case 5 : b += k[4];
		case 4 : a += ( (unsigned)k[3] << 24 );
		case 3 : a += ( (unsigned)k[2] << 16 );
		case 2 : a += ( (unsigned)k[1] << 8 );  
		case 1 : a += k[0];
	}
	
	mix ( a, b, c );
	
	return c;
}
*/