QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#583448#9356. LRU Algorithmshift#TL 0ms3528kbC++201.4kb2024-09-22 19:58:292024-09-22 19:58:29

Judging History

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

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

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::unordered_set<int> s, R;
    for(int i = 0; i < n; i ++ ) {
        std::vector<bool> vis(n + 1);
        i64 h = 0;
        for(int j = i; j >= 0; j -- ) {
            if(not vis[a[j]]) {
                vis[a[j]] = true;
                h = (h * Base + a[j]) % P;
                s.insert(h);
            }
        }
        R.insert(h);
    }
    
    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.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: 3528kb

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: