#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
struct LL {
int key;
int val;
LL* next;
LL(int k, int v) : key(k), val(v), next(nullptr) {}
};
class LRUCache{
void exchange(LL* node, LL* next)
{
int key = node->key;
int nkey = next->key;
node->next = next->next;
next->next = nullptr;
last->next = next;
last = next;
// swap content
swap(next->key, node->key);
swap(next->val, node->val);
data.at(nkey) = node;
data.at(key) = next;
}
public:
LRUCache(int capacity) {
c_ = capacity;
head = nullptr;
last = nullptr;
}
int get(int key) {
if(data.count(key))
{
auto node = data.at(key); // the
int val = node->val;
auto next = node->next;
if(next)
{
exchange(node, next);
if(key == node->key)return -2;
}
return val;
}
else
return -1;
}
void set(int key, int value) {
if(!data.count(key))
{
LL* node = new LL(key, value);
data[key] = node;
if(head == nullptr) // empty
head = node, last = node;
else
{
last->next = node;
last = node;
}
}
else
{
auto node = data.at(key);
node->val = value;
auto next = node->next;
if(next)
{
exchange(node, next);
if(node->key == key)cout << '!';
}
}
// renew cache
if(data.size() > c_)
{
auto node = head;
head = head->next;
data.erase(node->key);
delete node;
}
}
int c_;
unordered_map<int, LL*> data;
LL* head, *last;
};
int main() {
LRUCache q(10);
//q.set(10,13);
//q.set(3,17);
//q.set(6,11);
//q.set(10,5);
//q.set(9,10);
//q.get(13);
//q.set(2,19);
//q.get(2);
//q.get(3);
//q.set(5,25);
//q.get(8);
//q.set(9,22);
//q.set(5,5);
//q.set(1,30);
//q.get(11);
q.set(9,12);
q.get(7);
q.get(5);
q.get(8);
q.get(9);
q.set(4,30);
q.set(9,3);
q.get(9);
q.get(10);
q.get(10);
q.set(6,14);
q.set(3,1);
q.get(3);
q.set(10,11);
q.get(8);
q.set(2,14);
q.get(1);
q.get(5);
q.get(4);
q.set(11,4);
q.set(12,24);
q.set(5,18);
q.get(13);
q.set(7,23);
q.get(8);
q.get(12);
q.set(3,27);
q.set(2,12);
q.get(5);
q.set(2,9);
q.set(13,4);
q.set(8,18);
q.set(1,7);
q.get(6);
cout << q.get(6) << ' ' << q.get(1) << endl;
// your code goes here
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgoKc3RydWN0IExMIHsKICAgIGludCBrZXk7CiAgICBpbnQgdmFsOwogICAgTEwqIG5leHQ7CiAgICBMTChpbnQgaywgaW50IHYpIDoga2V5KGspLCB2YWwodiksIG5leHQobnVsbHB0cikge30KfTsKCmNsYXNzIExSVUNhY2hlewogICAgICAgIAogICAgdm9pZCBleGNoYW5nZShMTCogbm9kZSwgTEwqIG5leHQpCiAgICB7CiAgICAgICAgaW50IGtleSA9IG5vZGUtPmtleTsKICAgICAgICBpbnQgbmtleSA9IG5leHQtPmtleTsKICAgICAgICBub2RlLT5uZXh0ID0gbmV4dC0+bmV4dDsKICAgICAgICBuZXh0LT5uZXh0ID0gbnVsbHB0cjsKICAgICAgICBsYXN0LT5uZXh0ID0gbmV4dDsKICAgICAgICBsYXN0ID0gbmV4dDsKICAgICAgICAgICAgICAgIAogICAgICAgIC8vIHN3YXAgY29udGVudAogICAgICAgIHN3YXAobmV4dC0+a2V5LCBub2RlLT5rZXkpOwogICAgICAgIHN3YXAobmV4dC0+dmFsLCBub2RlLT52YWwpOwogICAgICAgIGRhdGEuYXQobmtleSkgPSBub2RlOwogICAgICAgIGRhdGEuYXQoa2V5KSA9IG5leHQ7CiAgICB9CiAgICAKcHVibGljOgogICAgTFJVQ2FjaGUoaW50IGNhcGFjaXR5KSB7CiAgICAgICAgY18gPSBjYXBhY2l0eTsKICAgICAgICBoZWFkID0gbnVsbHB0cjsKICAgICAgICBsYXN0ID0gbnVsbHB0cjsKICAgIH0KICAgIAogICAgaW50IGdldChpbnQga2V5KSB7CiAgICAgICAgaWYoZGF0YS5jb3VudChrZXkpKQogICAgICAgIHsKICAgICAgICAgICAgYXV0byBub2RlID0gZGF0YS5hdChrZXkpOyAgLy8gdGhlCiAgICAgICAgICAgIGludCB2YWwgPSBub2RlLT52YWw7CiAgICAgICAgICAgIGF1dG8gbmV4dCA9IG5vZGUtPm5leHQ7CiAgICAgICAgICAgIAogICAgICAgICAgICBpZihuZXh0KQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBleGNoYW5nZShub2RlLCBuZXh0KTsKICAgICAgICAgICAgICAgIGlmKGtleSA9PSBub2RlLT5rZXkpcmV0dXJuIC0yOwogICAgICAgICAgICB9CiAgICAgICAgICAgIAogICAgICAgICAgICByZXR1cm4gdmFsOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgICAgIHJldHVybiAtMTsKICAgIH0KCiAgICAKICAgIHZvaWQgc2V0KGludCBrZXksIGludCB2YWx1ZSkgewogICAgICAgIGlmKCFkYXRhLmNvdW50KGtleSkpCiAgICAgICAgewogICAgICAgICAgICBMTCogbm9kZSA9IG5ldyBMTChrZXksIHZhbHVlKTsKICAgICAgICAgICAgZGF0YVtrZXldID0gbm9kZTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGlmKGhlYWQgPT0gbnVsbHB0cikgLy8gZW1wdHkKICAgICAgICAgICAgICAgIGhlYWQgPSBub2RlLCBsYXN0ID0gbm9kZTsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBsYXN0LT5uZXh0ID0gbm9kZTsKICAgICAgICAgICAgICAgIGxhc3QgPSBub2RlOwogICAgICAgICAgICB9CiAgICAgICAgICAgIAogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBhdXRvIG5vZGUgPSBkYXRhLmF0KGtleSk7CiAgICAgICAgICAgIG5vZGUtPnZhbCA9IHZhbHVlOwogICAgICAgICAgICBhdXRvIG5leHQgPSBub2RlLT5uZXh0OwogICAgICAgICAgICBpZihuZXh0KQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBleGNoYW5nZShub2RlLCBuZXh0KTsKICAgICAgICAgICAgICAgIGlmKG5vZGUtPmtleSA9PSBrZXkpY291dCA8PCAnISc7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgCiAgICAgICAgLy8gcmVuZXcgY2FjaGUKICAgICAgICBpZihkYXRhLnNpemUoKSA+IGNfKQogICAgICAgIHsKICAgICAgICAgICAgYXV0byBub2RlID0gaGVhZDsKICAgICAgICAgICAgaGVhZCA9IGhlYWQtPm5leHQ7CiAgICAgICAgICAgIGRhdGEuZXJhc2Uobm9kZS0+a2V5KTsKICAgICAgICAgICAgZGVsZXRlIG5vZGU7CiAgICAgICAgfQogICAgfQogICAgCiAgICBpbnQgY187CiAgICB1bm9yZGVyZWRfbWFwPGludCwgTEwqPiBkYXRhOwogICAgTEwqIGhlYWQsICpsYXN0Owp9OwoKaW50IG1haW4oKSB7CglMUlVDYWNoZSBxKDEwKTsKCS8vcS5zZXQoMTAsMTMpOwoJLy9xLnNldCgzLDE3KTsKCS8vcS5zZXQoNiwxMSk7CgkvL3Euc2V0KDEwLDUpOwoJLy9xLnNldCg5LDEwKTsKCS8vcS5nZXQoMTMpOwoJLy9xLnNldCgyLDE5KTsKCS8vcS5nZXQoMik7CgkvL3EuZ2V0KDMpOwoJLy9xLnNldCg1LDI1KTsKCS8vcS5nZXQoOCk7CgkvL3Euc2V0KDksMjIpOwoJLy9xLnNldCg1LDUpOwoJLy9xLnNldCgxLDMwKTsKCS8vcS5nZXQoMTEpOwoJcS5zZXQoOSwxMik7CglxLmdldCg3KTsKCXEuZ2V0KDUpOwoJcS5nZXQoOCk7CglxLmdldCg5KTsKCXEuc2V0KDQsMzApOwoJcS5zZXQoOSwzKTsKCXEuZ2V0KDkpOwoJcS5nZXQoMTApOwoJcS5nZXQoMTApOwoJCgkKCXEuc2V0KDYsMTQpOwoJcS5zZXQoMywxKTsKCXEuZ2V0KDMpOwoJcS5zZXQoMTAsMTEpOwoJcS5nZXQoOCk7CglxLnNldCgyLDE0KTsKCXEuZ2V0KDEpOwoJcS5nZXQoNSk7CglxLmdldCg0KTsKCXEuc2V0KDExLDQpOwoJcS5zZXQoMTIsMjQpOwoJcS5zZXQoNSwxOCk7CglxLmdldCgxMyk7CglxLnNldCg3LDIzKTsKCXEuZ2V0KDgpOwoJcS5nZXQoMTIpOwoJcS5zZXQoMywyNyk7CglxLnNldCgyLDEyKTsKCXEuZ2V0KDUpOwoJcS5zZXQoMiw5KTsKCXEuc2V0KDEzLDQpOwoJcS5zZXQoOCwxOCk7CglxLnNldCgxLDcpOwoJcS5nZXQoNik7Cgljb3V0IDw8IHEuZ2V0KDYpIDw8ICcgJyA8PCBxLmdldCgxKSA8PCBlbmRsOwoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJcmV0dXJuIDA7Cn0=