[2019 우 객 여름 다 교 3 차 전] J 문제 LRU management

제목 링크
제목
좋아, 이 문 제 를 나 는 사실 보지 도 못 했 어. 팀 원 들 이 나 에 게 이 문 제 는 모 의 문제 라 고 말 해서 시간 이 걸린다 고 했 어.그리고 나 서 나 는 올 라 갔다..............................................................................만약 나타 나 지 않 았 다 면, 그것 을 표 끝 에 끼 워 넣 으 세 요.삽입 후 선형 표 길이 가 m 를 초과 하 는 것 을 발견 하면 표 두 의 요 소 를 팝 업 합 니 다.검색 할 때 이 값 (string) 이 있 으 면 요구 에 따라 이 값 (string) 의 이전 또는 다음 을 조회 하고 값 (int) 을 되 돌려 줍 니 다. (이전 또는 다음 도 없 으 면) 출력: Invalid
분석 하 다.
처음에는 이게... STL 로 폭력 을 행사 할 수 있 을 거 라 고 생각 했 는데 (물론 너무 폭력 적 이면 안 되 죠) 저 는 unordered 를 선 택 했 습 니 다.map + list 맵 으로 T 를 할 수 있다 고 들 었 는데 안 해 봤 어 요... unorderedmap 는 해시 표 이 고 map 는 빨 간 검 은 나무 입 니 다. 상대 적 으로 map 의 조회, 삽입, 삭제 시간 이 안정 적 이 고 모두 O (logN) 이 며 unordered 입 니 다.map 의 시간 불확실 성 이 비교적 크 고 운 이 좋 으 면 O (1) 의 조회 이 며 운 이 나 쁘 면 O (N) 입 니 다.
복잡 도 는 평균 상수 이 고 최 악의 경우 용기 크기 와 선형 이다.cppreference 에서 발췌
unordered_map 는 string 을 색인 으로 하여 list 의 교체 기 list 를 저장 하여 값 의 순 서 를 저장 하 였 습 니 다. string 과 int 두 변 수 를 포함 하 였 으 나 제 가 첫 발 에 T 를 넣 었 습 니 다. 그리고 빨리 읽 으 면 AC 가 됩 니 다. 카드 가 끊 긴 것 같 습 니 다.
AC 코드

#include 

using namespace std;

typedef list<pair<int, string>>::iterator pl;
unordered_map<string, pl> ump;
list<pair<int, string>> lists;
char catchmessage[100];

struct ioss
{
#define endl '
'
    static const int LEN = 20000000;
    char obuf[LEN], *oh = obuf;
    std::streambuf *fb;
    ioss()
    {
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        fb = cout.rdbuf();
    }
    inline char gc()
    {

        static char buf[LEN], *s, *t, buf2[LEN];
        return (s == t) && (t = (s = buf) + fread(buf, 1, LEN, stdin)), s == t ? -1 : *s++;
    }
    inline ioss &operator>>(long long &x)
    {
        static char ch, sgn, *p;
        ch = gc(), sgn = 0;
        for (; !isdigit(ch); ch = gc())
        {
            if (ch == -1)
                return *this;
            sgn |= ch == '-';
        }
        for (x = 0; isdigit(ch); ch = gc())
            x = x * 10 + (ch ^ '0');
        sgn && (x = -x);
        return *this;
    }
    inline ioss &operator>>(int &x)
    {
        static char ch, sgn, *p;
        ch = gc(), sgn = 0;
        for (; !isdigit(ch); ch = gc())
        {
            if (ch == -1)
                return *this;
            sgn |= ch == '-';
        }
        for (x = 0; isdigit(ch); ch = gc())
            x = x * 10 + (ch ^ '0');
        sgn && (x = -x);
        return *this;
    }
    inline ioss &operator>>(char &x)
    {
        static char ch;
        for (; !isalpha(ch); ch = gc())
        {
            if (ch == -1)
                return *this;
        }
        x = ch;
        return *this;
    }
    inline ioss &operator>>(string &x)
    {
        static char ch, *p, buf2[LEN];
        for (; !isalpha(ch) && !isdigit(ch); ch = gc())
            if (ch == -1)
                return *this;
        p = buf2;
        for (; isalpha(ch) || isdigit(ch); ch = gc())
            *p = ch, p++;
        *p = '\0';
        x = buf2;
        return *this;
    }
    inline ioss &operator<<(string &c)
    {
        for (auto &p : c)
            this->operator<<(p);
        return *this;
    }
    inline ioss &operator<<(const char *c)
    {
        while (*c != '\0')
        {
            this->operator<<(*c);
            c++;
        }
        return *this;
    }
    inline ioss &operator<<(const char &c)
    {
        oh == obuf + LEN ? (fb->sputn(obuf, LEN), oh = obuf) : 0;
        *oh++ = c;
        return *this;
    }
    inline ioss &operator<<(int x)
    {
        static int buf[30], cnt;
        if (x < 0)
            this->operator<<('-'), x = -x;
        if (x == 0)
            this->operator<<('0');
        for (cnt = 0; x; x /= 10)
            buf[++cnt] = x % 10 | 48;
        while (cnt)
            this->operator<<((char)buf[cnt--]);
        return *this;
    }
    inline ioss &operator<<(long long x)
    {
        static int buf[30], cnt;
        if (x < 0)
            this->operator<<('-'), x = -x;
        if (x == 0)
            this->operator<<('0');
        for (cnt = 0; x; x /= 10)
            buf[++cnt] = x % 10 | 48;
        while (cnt)
            this->operator<<((char)buf[cnt--]);
        return *this;
    }
    ~ioss()
    {
        fb->sputn(obuf, oh - obuf);
    }
} io;

int main()
{
#ifdef ACM_LOCAL
    freopen("./in.txt", "r", stdin);
    freopen("./out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    int t;
    io >> t;
    while (t--)
    {
        ump.clear();
        lists.clear();
        int q, m;
        io >> q >> m;
        string s;
        int op, val;
        for (int i = 0; i < q; i++)
        {
            pl cur;
            io >> op >> s >> val;
            if (op)
            {
                if (!ump.count(s))
                {
                    cout << "Invalid" << endl;
                    continue;
                }
                cur = ump[s];
                if (val == 1)
                {
                    cur++;
                    if (cur == lists.end())
                    {
                        cout << "Invalid" << endl;
                        continue;
                    }
                }
                else if (val == -1)
                {
                    if (cur == lists.begin())
                    {
                        cout << "Invalid" << endl;
                        continue;
                    }
                    cur--;
                }
                cout << (*cur).first << endl;
            }
            else
            {
                if (!ump.count(s))
                {
                    pair<int, string> newnode = make_pair(val, s);
                    lists.push_back(newnode);
                    pl tmp = lists.end();
                    tmp--;
                    ump.insert(make_pair(s, tmp));
                    if (lists.size() > m)
                    {
                        ump.erase(lists.front().second);
                        lists.pop_front();
                    }
                    cout << val << endl;
                    continue;
                }
                cur = ump[s];
                pair<int, string> newnode = make_pair((*cur).first, s);
                lists.push_back(newnode);
                pl tmp = lists.end();
                tmp--;
                ump[s] = tmp;
                lists.erase(cur);
                cout << newnode.first << endl;
            }
        }
    }
    return 0;
}