21 Days Training // Day 12

T2. hashing

My idea : enum.

For every new code, search all previous codes and compare, and then count.

Code :

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("hashing.in", "r", stdin);
    freopen("hashing.out", "w", stdout);
    int N;cin >> N;
    vector<bitset<65> > hsh;

    unsigned long long H;
    bitset<65> HC, C;
    for (int i=0;i<N;i++) {
        HC=0;
        C=0;
        cin >> H;
        for (int j=0;j<=64&&H!=0;j++) {
            HC[j] = H&1;
            H>>=1;
        }
        int count=0;
        for (int j=0;j<=i-1;j++) {
            C = hsh[j];
            int df=0;
            for (int k=0;k<=64;k++) df += (C[k]!=HC[k]);
            if (df!=3) continue;
            count++;
        }
        cout << count << endl;
        hsh.push_back(HC);
    }
    return 0;
}

Complexity : O(\frac{n^2}{w})
Constraints :

Expected : 0/30