860.cpp

// 860 - LRU Cache
//
// 使用 std::list + std::unordered_map 實作 LRU Cache
// list 的順序即為 age 順序：front = age 0（最近使用），back = age n-1（最久未使用）
//
// Hit:  將該元素 splice 到 list 最前面 → O(1)
// Miss: pop_back（淘汰 age 最大的），push_front（新元素）→ O(1)
// 查找: unordered_map 存 value → iterator 的映射 → O(1)
//
// 每個 test case 總時間複雜度 O(n + m)

#include <iostream>
#include <list>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    while (cin >> n >> m) {
        // cache: 雙向鏈結串列，front = age 0，back = age n-1
        list<int> cache;
        // pos: 記錄每個值在 list 中的 iterator，用於 O(1) 查找與搬移
        unordered_map<int, list<int>::iterator> pos;

        // 讀取初始 cache 狀態（依 age 遞增順序輸入）
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            cache.push_back(x);
        }
        // 建立 hash map：value → 對應的 list iterator
        for (auto it = cache.begin(); it != cache.end(); ++it) {
            pos[*it] = it;
        }

        string result;

        for (int q = 0; q < m; q++) {
            int x;
            cin >> x;

            auto it = pos.find(x);
            if (it != pos.end()) {
                // ===== Hit =====
                // 將此元素搬到 list 最前面（age 設為 0）
                // splice 不會使 iterator 失效，所以 pos 中的 iterator 仍然有效
                result += '1';
                cache.splice(cache.begin(), cache, it->second);
            } else {
                // ===== Miss =====
                // 淘汰 list 最後面的元素（age 最大 = 最久未使用）
                result += '0';
                int evicted = cache.back();
                pos.erase(evicted);
                cache.pop_back();
                // 新元素放到最前面（age = 0）
                cache.push_front(x);
                pos[x] = cache.begin();
            }
        }

        // 輸出所有查詢的 hit/miss 結果（1=hit, 0=miss）
        cout << result << "\n";

        // 輸出 cache 內容，依 age 遞增順序（front → back）
        bool first = true;
        for (int val : cache) {
            if (!first) cout << " ";
            first = false;
            cout << val;
        }
        cout << "\n";
    }

    return 0;
}