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

class HashTable {
private:
    
    const float LOAD_FACTOR_LIMIT = 0.5;
    
    vector<pair<int, int>> table;
    vector<int> state;
    int tableSize, numberOfElements;

    int Hash(int key) {
        return key % tableSize;
    }

    void rehash() {
        tableSize *= 2;
        vector<pair<int, int>> newTable(tableSize);
        vector<int> newState(tableSize);
        for (int i = 0; i < tableSize / 2; i++) {
            if (state[i] == 1) {
                int idx = Hash(table[i].first);
                while (newState[idx] == 1) {
                    idx = (idx + 1) % tableSize;
                }
                newTable[idx] = table[i];
                newState[idx] = 1;
            }
        }
        table = newTable;
        state = newState;
    }

    void update(int key, int val) {
        int idx = Hash(key);
        for (int i = 0; i < tableSize && state[idx] != 0; i++) {
            if (state[idx] == 1 && table[idx].first == key) {
                table[idx].second = val;
                return;
            }
            idx = (idx + 1) % tableSize;
        }
    }

public:
    HashTable() {
        tableSize = 8;
        table.resize(tableSize);
        state.resize(tableSize);
        numberOfElements = 0;
    }

    void insert(int key, int value) {
        if (get(key)) {
            update(key, value);
            return;
        }
        float currentLoadFactor = 1.0 * numberOfElements / tableSize;
        if (currentLoadFactor >= LOAD_FACTOR_LIMIT) rehash();
        int idx = Hash(key);
        while (state[idx] == 1) {
            idx = (idx + 1) % tableSize;
        }
        table[idx] = {key, value};
        state[idx] = 1;
        numberOfElements++;
    }

    int get(int key) {
        int idx = Hash(key);
        for (int i = 0; i < tableSize && state[idx] != 0; i++) {
            if (state[idx] == 1 && table[idx].first == key) {
                return table[idx].second;
            }
            idx = (idx + 1) % tableSize;
        }
        return 0;
    }

    void addOne(int key) {
        insert(key, get(key) + 1);
    }

    void remove(int key) {
        int idx = Hash(key);
        for (int i = 0; i < tableSize && state[idx] != 0; i++) {
            if (state[idx] == 1 && table[idx].first == key) {
                state[idx] = -1;
                numberOfElements--;
                return;
            }
            idx = (idx + 1) % tableSize;
        }
    }

    int size() {
        return numberOfElements;
    }

    bool empty() {
        return numberOfElements == 0;
    }

    void print() {
        for (int i = 0; i < tableSize; i++) {
            if (state[i] == 1) cout << "(" << table[i].first << ", " << table[i].second << ") ";
            else if (state[i] == 0) cout << "NOT_USED ";
            else cout << "DELETED ";
        }
    }
};

int main()
{
    HashTable h;
    h.insert(1, 1);
    h.insert(2, 2);
    h.insert(3, 3);
    h.insert(4, 4);
    h.insert(5, 4);
    h.insert(101, 4);
    h.insert(100, 4);

    h.insert(110, 4);

    h.insert(110, 5);
    h.addOne(110);
    h.remove(110);
    h.remove(101);
    h.remove(100);

    h.insert(100, 5);



    h.print();
    return 0;
}