链表+hash

链表：便于pop_back()删去末尾缓存行 l.back()取末尾缓存行内存编号，push_front()将新取的缓存行放入首行

hash映射：unordered_map<int,Block> hamp,Block.it迭代器，Block.f表示是否被写； 便于hmap.count()查找内存是否存在该缓存(O(1))，hamp[a]便于直接找到缓存的位置（iterator迭代器，是否被写）

注：替换不是放到缓存行最后，而是放到行首 缓存替换+lru比较复杂，建议先在网上学下，自己动手模拟下

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <unordered_map>
using namespace std;

struct Block{
    list<int>::iterator it;
    bool f = false;
};

int main(){
    int n,N,t;
    cin>>n>>N>>t;
    int op,a;
    vector<list<int>> lru(N);
    vector<unordered_map<int,Block>> hmap(N);

    while(t--){
        cin>>op>>a;
        int grp = (a/n)%N;
        auto& L = lru[grp];
        auto& T = hmap[grp];

        if(T.count(a)){//命中
            auto& itr = T[a].it;
            L.erase(itr);
            L.push_front(a);
            T[a].it = L.begin();
            if(op == 1) T[a].f = true;
        }
        else{//未命中
            if(L.size()==n){//full
                if(T[L.back()].f == true){
                    cout<<1<<' '<<L.back()<<endl;
                }
                T.erase(L.back());
                L.pop_back();
                L.push_front(a);
                T[a].it = L.begin();
                if(op == 1) T[a].f = true;
                cout<<0<<' '<<a<<endl;
            }
            else{//未命中，没满
                L.push_front(a);
                cout<<0<<' '<<a<<endl;
                T[a].it = L.begin();
                if(op == 1) T[a].f = true;
            }
        }
    }
}