Cod sursa(job #1043841)

Utilizator raulstoinStoin Raul raulstoin Data 28 noiembrie 2013 23:17:33
Problema Dtcsu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>

#define NMAX 276997
#define LL long long
#define ULL unsigned LL

using namespace std;

FILE *fin,*fout;

int q,sol;
LL n,nr;
vector<LL> v;
const int index64[64] = {
    0,  1, 48,  2, 57, 49, 28,  3,
   61, 58, 50, 42, 38, 29, 17,  4,
   62, 55, 59, 36, 53, 51, 43, 22,
   45, 39, 33, 30, 24, 18, 12,  5,
   63, 47, 56, 27, 60, 41, 37, 16,
   54, 35, 52, 21, 44, 32, 23, 11,
   46, 26, 40, 15, 34, 20, 31, 10,
   25, 14, 19,  9, 13,  8,  7,  6
};

const int SZ=100000;
char input[SZ+1],*in;

inline int bitScanForward(ULL bb) {
   const ULL debruijn64 = 0x03f79d71b4cb0a89LL;
   return index64[((bb & -bb) * debruijn64) >> 58];
}

inline LL conv()
{
	LL nr=0;
	for(;!(*in>='0' && *in<='9') && *in;in++);
	if(in==input+SZ)
	{
		fread(input,1,SZ,fin);
		in=input;
	}
	for(;*in>='0' && *in<='9';in++)
	{
		nr=nr*10+(*in-'0');
		if(in+1==input+SZ)
		{
			fread(input,1,SZ,fin);
			in=input-1;
		}
	}
	return nr;
}

int main()
{
	fin=fopen("dtcsu.in","r");
	fout=fopen("dtcsu.out","w");
	fread(input,1,SZ,fin);
	in=input;
	for(int i=0;i<NMAX;i++)
	{
		n=conv();
		if(!(n&1))
			continue;
		v.push_back(n);
	}
	sort(v.begin(),v.end());
	q=conv();
	for(int r;q;q--)
	{
		n=conv();
		r=bitScanForward(n);
		n>>=r;
		sol+=(binary_search(v.begin(),v.end(),n));
	}
	fprintf(fout,"%d",sol);
	return 0;
}