QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#583406#9356. LRU Algorithmshift#TL 0ms3556kbC++202.2kb2024-09-22 19:50:542024-09-22 19:50:56

Judging History

你现在查看的是最新测评结果

  • [2024-09-26 19:14:31]
  • hack成功,自动添加数据
  • (/hack/913)
  • [2024-09-26 19:12:47]
  • hack成功,自动添加数据
  • (/hack/912)
  • [2024-09-22 19:50:56]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3556kb
  • [2024-09-22 19:50:54]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int Base = 1145141;
constexpr int P = 998244353;

void solve() {
    int n, q;
    std::cin >> n >> q;

    std::vector<i64> h(n + 1), a(n);
    for(int i = 0; i < n; i ++ ) {
        std::cin >> a[i];
    }

    std::vector<std::set<i64>> s(n);
    for(int i = 0; i < n; i ++ ) {
        std::vector<bool> vis(n + 1);
        i64 h = 0, cnt = -1;
        for(int j = i; j >= 0; j -- ) {
            if(not vis[a[j]]) {
                vis[a[j]] = true;
                cnt += 1;
                h = (h * Base + a[j]) % P;
                s[cnt].insert(h);
            }
        }
    }

    auto calc = [&](std::deque<int> q) -> i64 {
        i64 h = 0;
        while(q.size()) {
            h = (h * Base + q.front()) % P;
            q.pop_front();
        }
        return h;
    };
    
    std::set<i64> R;
    std::deque<int> Q;
    std::vector<bool> have(n + 1);
    for(int i = 0; i < n; i ++ ) {
        if(not have[a[i]]) {
            have[a[i]] = true;
            Q.push_front(a[i]);
        } else {
            std::deque<int> r;
            while(Q.front() != a[i]) {
                r.push_back(Q.front());
                Q.pop_front();
            }
            Q.pop_front();
            while(r.size()) {
                Q.push_front(r.back());
                r.pop_back();
            }
            Q.push_front(a[i]);
        }
        R.insert(calc(Q));
    }
    
    while(q -- ) {
        int t;
        std::cin >> t;
        bool f = false;
        std::vector<int> ask;
        for(int i = 0; i < t; i ++ ) {
            int x;
            std::cin >> x;
            if(x) ask.push_back(x);
            else f = true;
        }

        i64 h = 0;
        for(auto x : ask) {
            h = (h * Base + x) % P;
        }
        if(f) {
            std::cout << (R.count(h) ? "Yes" : "No") << '\n';
        } else {
            std::cout << (s[t - 1].count(h) ? "Yes" : "No") << '\n';
        }
    }

}

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

    int T = 1;
    std::cin >> T;
    while(T -- ) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3556kb

input:

1
7 5
4 3 4 2 3 1 4
1 4
2 2 3
3 3 2 1
4 4 1 3 2
4 3 4 0 0

output:

Yes
No
No
Yes
Yes

result:

ok 5 lines

Test #2:

score: -100
Time Limit Exceeded

input:

105
50 10
23 30 34 20 27 11 21 29 12 7 21 42 45 48 8 15 6 16 19 35 16 14 29 11 31 18 22 4 45 22 14 4 13 40 43 48 27 15 15 15 15 10 15 11 31 37 34 34 50 14
1 25
2 23 6
3 29 21 11
4 12 29 18 39
5 29 21 11 27 20
6 21 10 9 3 34 14
7 49 36 36 43 50 50 35
8 12 29 21 11 27 20 34 30
9 11 27 20 34 30 23 0 0 ...

output:


result: