Cod sursa(job #1033989)

Utilizator Teodor94Teodor Plop Teodor94 Data 17 noiembrie 2013 16:47:37
Problema Dtcsu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
#include <tr1/unordered_map>

using namespace std;
using namespace std::tr1;

#define TOTAL 276997
#define LEN 20
#define ll long long

char s[LEN];
ll p2[6];
int exp[6] = { 1, 2, 4, 8, 16, 32 };
unordered_map< int, int > h;

bool is_digit( char c ) {
    return c >= '0' && c <= '9';
}

ll get_int( char A[] ) {
    ll x = 0;
    int i = 0;
    while ( is_digit( A[i] ) ) {
        x = ( ll ) x * 10 + ( A[i] - '0' );
        ++i;
    }
    return x;
}

void read( FILE *fin ) {
    for ( int i = 0; i < TOTAL; ++i ) {
        fgets( s, LEN, fin );
        ll x = get_int( s );

        if ( x & 1 )
            ++h[x];
    }
}

void pregen() {
    p2[0] = 2;
    for ( int i = 1; i < 6; ++i )
        p2[i] = ( ll ) p2[i - 1] * p2[i - 1];
}

int main() {
    FILE *fin, *fout;

    fin = fopen( "dtcsu.in", "r" );
    fout = fopen( "dtcsu.out", "w" );

    read( fin );
    pregen();
    
    int q, ans = 0;
    fscanf( fin, "%d\n", &q );
    while ( q ) {
        fgets( s, LEN, fin );
        ll x = get_int( s );
        
        if ( !( x & 1 ) ) {
            for ( int i = 5; i >= 0; --i )
                if ( ( x & p2[i] - 1 ) == 0 )
                    x >>= exp[i];
        }

        unordered_map< int, int >::iterator it = h.find( x );
        if ( it != h.end() )
            ++ans;

        --q;
    }
    
    fprintf( fout, "%d\n", ans );
    fclose( fin );
    fclose( fout );
}