#include <iostream>
#include <vector>
#include <random>
#include <list>
using namespace std;

void izpisi(vector<int> v) {
    for (int x : v) cout << x << " ";
    cout << endl;
}

class HashTable {
public:
    vector<list<pair<int,int>>> t;
    int capacity, n;
    int hash(int x) { return x%capacity; }
    HashTable() { n=0; capacity=1; t.resize(capacity); }

    void rehash() {
        capacity *= 2;
        vector<list<pair<int,int>>> t2(capacity);
        for (int h=0;h<t.size();h++) {
            for (auto [key,value] : t[h]) {
                int h2 = hash(key);
                t2[h2].push_back({key,value});
            }
        }
        t = t2;
    }

    void insert(int k, int v) {
        if (n == capacity) rehash();  // alfa = 1
        int h=hash(k);
        for (auto& [key, value] : t[h]) {
            if (k==key) { value=v; return; }
        }
        t[h].push_back({k,v});
        n++;
    }

    int get(int k) {
        int h=hash(k);
        for (auto& [key, value] : t[h]) {
            if (k==key) { return value; }
        }
        return -1;
    }
};


int main() {
    default_random_engine rnd(123);
    HashTable ht;
    int st=1'000'000;
    for (int i=0;i<st;i++) {
        ht.insert(rnd()%1000000000, 1);
    }
    cout << ht.n << " " << ht.capacity << endl;
    return 0;
}