#include <iostream>
#include <cstdlib>
#include <ctime>
#include <bitset>
#include <set>
#include <algorithm>
using namespace std;
#pragma comment(linker, "/STACK:1677721600")
class CuckooHashTable {//set like - no duplicates
public:
static const int MAXP = 666013, MULT = 10;
private:
set<int> stash;
static const int D = 2;
int A[D];
int B[D];
int kt[MULT];
int T[MULT][MAXP];
bitset<MAXP> u[MULT];
int perm[2][32];
int hash(int idx, int x) {
int xnou = 0;
for(int i = 0; i < 32; i++) {
xnou = (xnou << 1) + ((x & (1 << perm[idx][31 - i])) >> perm[idx][31 - i]);
}
xnou = ((xnou % MAXP) + MAXP) % MAXP;
return xnou;
}
bool insert_in_free(int i, int x, int h1, int h2) {
if(!u[i][h1]) {
u[i][h1].flip();
T[i][h1] = x;
return true;
}
else if(!u[i][h2]){
u[i][h2].flip();
T[i][h2] = x;
return true;
}
return false;
}
public:
CuckooHashTable() {
srand(time(NULL));
bool must_continue = true;
for(int i = 0; i < MULT; i++) {
kt[i] = 0;
}
while(must_continue) {
for(int i = 0; i < D; i++) {
A[i] = rand() % 100;
B[i] = rand() % (i == 0? 100 : 10000);
}
for(int i = 0; i < D && must_continue; i++) {
for(int j = i + 1; j < D && must_continue; j++) {
if(A[i] != A[j] || B[i] != B[j]) {
must_continue = false;
}
}
}
}
for(int i = 0; i < 32; i++) {
perm[0][i] = i;
perm[1][i] = i;
}
random_shuffle(perm[0], perm[0] + 32);
random_shuffle(perm[1], perm[1] + 32);
}
void clearStash() {
stash.clear();
}
int stashSize() {
return stash.size();
}
int getFill(int y) {
return kt[y];
}
int dfs(int i, int x, int h, int depth) {
if(!u[i][h]) { u[i][h] = true; T[i][h] = x; return true;}
if(depth > 0) {
int hf = hash(0, T[i][h]);
hf = (hf == h ? hash(1, T[i][h]) : hf);
if(dfs(i, T[i][h], hf, depth - 1)) {
T[i][h] = x;
return true;
}
}
return false;
}
void insert(int x) {//works with D = 2
if(has(x)) return;
int h1 = hash(0, x);
int h2 = hash(1, x);
bool success = false;
for(int i = 0; i < MULT; i++) {
success = insert_in_free(i, x, h1, h2);
if(!success) {
success = dfs(i, x, h1, 10);
}
if(!success) {
success = dfs(i, x, h2, 10);
}
if(success) {kt[i]++; return;}
}
if(!success) {
stash.insert(x);
}
}
bool has(int i, int x) {
int h1 = hash(0, x);
int h2 = hash(1, x);
return ((u[i][h1] && T[i][h1] == x) || (u[i][h2] && T[i][h2] == x));
}
bool has(int x) {
for(int i = 0; i < MULT; i++) {
if(has(i, x)) return true;
}
return (stash.find(x) != stash.end());
}
void erase(int i, int x) {
int h1 = hash(0, x);
int h2 = hash(1, x);
if(u[i][h1] && T[i][h1] == x) {
u[i][h1] = false;
}
if(u[i][h2] && T[i][h2] == x) {
u[i][h2] = false;
}
}
};
CuckooHashTable T;
int a[CuckooHashTable::MULT * CuckooHashTable::MAXP];
void generare(){
int x;
srand(time(0));
for(int i = 0; i < CuckooHashTable::MULT * CuckooHashTable::MAXP; i++) {
do{
x = rand() * (1 << 15) + rand();
} while(x < 0/* || T.has(x)*/);//!!!!!!!!!!!!!!!!!!!!
a[i] = x;
}
}
void insertInCuckoo() {
for(int i = 0; i < CuckooHashTable::MULT * CuckooHashTable::MAXP; i++) {
T.insert(a[i]);
}
}
set<int> s;
void insertInSet() {
cout << s.max_size() << endl;
for(int i = 0; i < CuckooHashTable::MULT * CuckooHashTable::MAXP; i++) {
s.insert(a[i]);
}
}
int main() {
cout << clock() << endl;
generare();
cout << clock() << endl;
insertInSet();
cout << clock() << endl;
insertInCuckoo();
cout << clock() << endl << endl;
cout <<( T.MULT * T.MAXP - T.stashSize()) * 100.0 / (T.MAXP * T.MULT) << endl << endl;
for(int i = 0; i < T.MULT; i++) {
cout <<(T.getFill(i) * 100.00 / T.MAXP) << endl;
}
T.clearStash();
s.clear();
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPGN0aW1lPgojaW5jbHVkZSA8Yml0c2V0PgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNwcmFnbWEgY29tbWVudChsaW5rZXIsICIvU1RBQ0s6MTY3NzcyMTYwMCIpCgpjbGFzcyBDdWNrb29IYXNoVGFibGUgey8vc2V0IGxpa2UgLSBubyBkdXBsaWNhdGVzCnB1YmxpYzoKICAgIHN0YXRpYyBjb25zdCBpbnQgTUFYUCA9IDY2NjAxMywgTVVMVCA9IDEwOwpwcml2YXRlOgoJc2V0PGludD4gc3Rhc2g7CglzdGF0aWMgY29uc3QgaW50IEQgPSAyOwoJaW50IEFbRF07CglpbnQgQltEXTsKCWludCBrdFtNVUxUXTsKCWludCBUW01VTFRdW01BWFBdOwoJYml0c2V0PE1BWFA+IHVbTVVMVF07CglpbnQgcGVybVsyXVszMl07CglpbnQgaGFzaChpbnQgaWR4LCBpbnQgeCkgewoJCWludCB4bm91ID0gMDsKCQlmb3IoaW50IGkgPSAwOyBpIDwgMzI7IGkrKykgewoJCQl4bm91ID0gKHhub3UgPDwgMSkgKyAoKHggJiAoMSA8PCBwZXJtW2lkeF1bMzEgLSBpXSkpID4+IHBlcm1baWR4XVszMSAtIGldKTsKCQl9CgkJeG5vdSA9ICgoeG5vdSAlIE1BWFApICsgTUFYUCkgJSBNQVhQOwoJCXJldHVybiB4bm91OwoJfQoJYm9vbCBpbnNlcnRfaW5fZnJlZShpbnQgaSwgaW50IHgsIGludCBoMSwgaW50IGgyKSB7CgkJaWYoIXVbaV1baDFdKSB7CgkJCXVbaV1baDFdLmZsaXAoKTsKCQkJVFtpXVtoMV0gPSB4OwoJCQlyZXR1cm4gdHJ1ZTsKCQl9CgkJZWxzZSBpZighdVtpXVtoMl0pewoJCQl1W2ldW2gyXS5mbGlwKCk7CgkJCVRbaV1baDJdID0geDsKCQkJcmV0dXJuIHRydWU7CgkJfQoJCXJldHVybiBmYWxzZTsKCX0KcHVibGljOgoJQ3Vja29vSGFzaFRhYmxlKCkgewoJCXNyYW5kKHRpbWUoTlVMTCkpOwoJCWJvb2wgbXVzdF9jb250aW51ZSA9IHRydWU7CgkJZm9yKGludCBpID0gMDsgaSA8IE1VTFQ7IGkrKykgewoJCQlrdFtpXSA9IDA7CgkJfQoJCXdoaWxlKG11c3RfY29udGludWUpIHsKCQkJZm9yKGludCBpID0gMDsgaSA8IEQ7IGkrKykgewoJCQkJQVtpXSA9IHJhbmQoKSAlIDEwMDsKCQkJCUJbaV0gPSByYW5kKCkgJSAoaSA9PSAwPyAxMDAgOiAxMDAwMCk7CgkJCX0KCQkJZm9yKGludCBpID0gMDsgaSA8IEQgJiYgbXVzdF9jb250aW51ZTsgaSsrKSB7CgkJCQlmb3IoaW50IGogPSBpICsgMTsgaiA8IEQgJiYgbXVzdF9jb250aW51ZTsgaisrKSB7CgkJCQkJaWYoQVtpXSAhPSBBW2pdIHx8IEJbaV0gIT0gQltqXSkgewoJCQkJCQltdXN0X2NvbnRpbnVlID0gZmFsc2U7CgkJCQkJfQoJCQkJfQoJCQl9CgkJfQoJCWZvcihpbnQgaSA9IDA7IGkgPCAzMjsgaSsrKSB7CgkJCXBlcm1bMF1baV0gPSBpOwoJCQlwZXJtWzFdW2ldID0gaTsKCQl9CgkJcmFuZG9tX3NodWZmbGUocGVybVswXSwgcGVybVswXSArIDMyKTsKCQlyYW5kb21fc2h1ZmZsZShwZXJtWzFdLCBwZXJtWzFdICsgMzIpOwoJfQoJdm9pZCBjbGVhclN0YXNoKCkgewoJCXN0YXNoLmNsZWFyKCk7Cgl9CglpbnQgc3Rhc2hTaXplKCkgewoJCXJldHVybiBzdGFzaC5zaXplKCk7Cgl9CglpbnQgZ2V0RmlsbChpbnQgeSkgewoJCXJldHVybiBrdFt5XTsKCX0KCWludCBkZnMoaW50IGksIGludCB4LCBpbnQgaCwgaW50IGRlcHRoKSB7CgkJaWYoIXVbaV1baF0pIHsJCXVbaV1baF0gPSB0cnVlOyBUW2ldW2hdID0geDsgcmV0dXJuIHRydWU7fQoJCWlmKGRlcHRoID4gMCkgewoJCQlpbnQgaGYgPSBoYXNoKDAsIFRbaV1baF0pOwoJCQloZiA9IChoZiA9PSBoID8gaGFzaCgxLCBUW2ldW2hdKSA6IGhmKTsKCQkJaWYoZGZzKGksIFRbaV1baF0sIGhmLCBkZXB0aCAtIDEpKSB7CgkJCQlUW2ldW2hdID0geDsKCQkJCXJldHVybiB0cnVlOwoJCQl9CgkJfQoJCXJldHVybiBmYWxzZTsKCX0KCXZvaWQgaW5zZXJ0KGludCB4KSB7Ly93b3JrcyB3aXRoIEQgPSAyCgkJaWYoaGFzKHgpKQlyZXR1cm47CgkJaW50IGgxID0gaGFzaCgwLCB4KTsKCQlpbnQgaDIgPSBoYXNoKDEsIHgpOwoJCWJvb2wgc3VjY2VzcyA9IGZhbHNlOwoJCWZvcihpbnQgaSA9IDA7IGkgPCBNVUxUOyBpKyspIHsKCQkJc3VjY2VzcyA9IGluc2VydF9pbl9mcmVlKGksIHgsIGgxLCBoMik7CgkJCWlmKCFzdWNjZXNzKSB7CgkJCQlzdWNjZXNzID0gZGZzKGksIHgsIGgxLCAxMCk7CgkJCX0KCQkJaWYoIXN1Y2Nlc3MpIHsKCQkJCXN1Y2Nlc3MgPSBkZnMoaSwgeCwgaDIsIDEwKTsKCQkJfQoJCQlpZihzdWNjZXNzKSB7a3RbaV0rKzsJcmV0dXJuO30KCQl9CgkJaWYoIXN1Y2Nlc3MpIHsKCQkJc3Rhc2guaW5zZXJ0KHgpOwoJCX0KCX0KCWJvb2wgaGFzKGludCBpLCBpbnQgeCkgewoJCWludCBoMSA9IGhhc2goMCwgeCk7CgkJaW50IGgyID0gaGFzaCgxLCB4KTsKCQlyZXR1cm4gKCh1W2ldW2gxXSAmJiBUW2ldW2gxXSA9PSB4KSB8fCAodVtpXVtoMl0gJiYgVFtpXVtoMl0gPT0geCkpOwoJfQoJYm9vbCBoYXMoaW50IHgpIHsKCQlmb3IoaW50IGkgPSAwOyBpIDwgTVVMVDsgaSsrKSB7CgkJCWlmKGhhcyhpLCB4KSkJcmV0dXJuIHRydWU7CgkJfQoJCXJldHVybiAoc3Rhc2guZmluZCh4KSAhPSBzdGFzaC5lbmQoKSk7Cgl9Cgl2b2lkIGVyYXNlKGludCBpLCBpbnQgeCkgewoJCWludCBoMSA9IGhhc2goMCwgeCk7CgkJaW50IGgyID0gaGFzaCgxLCB4KTsKCQlpZih1W2ldW2gxXSAmJiBUW2ldW2gxXSA9PSB4KSB7CgkJCXVbaV1baDFdID0gZmFsc2U7CgkJfQoJCWlmKHVbaV1baDJdICYmIFRbaV1baDJdID09IHgpIHsKCQkJdVtpXVtoMl0gPSBmYWxzZTsKCQl9Cgl9Cn07CgpDdWNrb29IYXNoVGFibGUgVDsKCgppbnQgYVtDdWNrb29IYXNoVGFibGU6Ok1VTFQgKiBDdWNrb29IYXNoVGFibGU6Ok1BWFBdOwoKdm9pZCBnZW5lcmFyZSgpewoJaW50IHg7CglzcmFuZCh0aW1lKDApKTsKCWZvcihpbnQgaSA9IDA7IGkgPCBDdWNrb29IYXNoVGFibGU6Ok1VTFQgKiBDdWNrb29IYXNoVGFibGU6Ok1BWFA7IGkrKykgewoJCWRvewoJCQl4ID0gcmFuZCgpICogKDEgPDwgMTUpICsgcmFuZCgpOwoJCX0gd2hpbGUoeCA8IDAvKiB8fCBULmhhcyh4KSovKTsvLyEhISEhISEhISEhISEhISEhISEhCgkJYVtpXSA9IHg7Cgl9Cn0KCnZvaWQgaW5zZXJ0SW5DdWNrb28oKSB7Cglmb3IoaW50IGkgPSAwOyBpIDwgQ3Vja29vSGFzaFRhYmxlOjpNVUxUICogQ3Vja29vSGFzaFRhYmxlOjpNQVhQOyBpKyspIHsKCQlULmluc2VydChhW2ldKTsKCX0KfQoKc2V0PGludD4gczsKCnZvaWQgaW5zZXJ0SW5TZXQoKSB7Cgljb3V0IDw8IHMubWF4X3NpemUoKSA8PCBlbmRsOwoJZm9yKGludCBpID0gMDsgaSA8IEN1Y2tvb0hhc2hUYWJsZTo6TVVMVCAqIEN1Y2tvb0hhc2hUYWJsZTo6TUFYUDsgaSsrKSB7CgkJcy5pbnNlcnQoYVtpXSk7Cgl9Cn0KCmludCBtYWluKCkgewoJY291dCA8PCBjbG9jaygpIDw8IGVuZGw7CglnZW5lcmFyZSgpOwoJY291dCA8PCBjbG9jaygpIDw8IGVuZGw7CglpbnNlcnRJblNldCgpOwoJY291dCA8PCBjbG9jaygpIDw8IGVuZGw7CglpbnNlcnRJbkN1Y2tvbygpOwoJY291dCA8PCBjbG9jaygpIDw8IGVuZGwgPDwgZW5kbDsKCWNvdXQgPDwoIFQuTVVMVCAqIFQuTUFYUCAtIFQuc3Rhc2hTaXplKCkpICogMTAwLjAgLyAoVC5NQVhQICogVC5NVUxUKSA8PCBlbmRsIDw8IGVuZGw7Cglmb3IoaW50IGkgPSAwOyBpIDwgVC5NVUxUOyBpKyspIHsKCQljb3V0IDw8KFQuZ2V0RmlsbChpKSAqIDEwMC4wMCAvIFQuTUFYUCkgPDwgZW5kbDsKCX0KCVQuY2xlYXJTdGFzaCgpOwoJcy5jbGVhcigpOwoJcmV0dXJuIDA7Cn0KCg==