#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;
}