QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#583619#9356. LRU Algorithmshift#RE 1ms3616kbC++202.2kb2024-09-22 20:52:332024-09-22 20:52:34

Judging History

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

  • [2024-09-26 19:14:31]
  • hack成功,自动添加数据
  • (/hack/913)
  • [2024-09-26 19:12:47]
  • hack成功,自动添加数据
  • (/hack/912)
  • [2024-09-22 20:52:34]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3616kb
  • [2024-09-22 20:52:33]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
#define int i64

bool isprime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int findPrime(int n) {
    while (!isprime(n)) {
        n++;
    }
    return n;
}

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int P = findPrime(rng() % 900000000 + 100000000);
const int Base = findPrime(rng() % 8000000 + 10000000);

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<bool> ans(q);
    std::unordered_map<int, std::vector<int>> q1, q2;
    for(int i = 0; i < q; i ++ ) {
        int t;
        std::cin >> t;

        i64 h = 0, f = true, cnt = 0;
        while(t -- ){
            int x;
            std::cin >> x;
            if(x) h = (h * Base + x) % P, cnt ++;
            else f = false;
        }
        assert(cnt > 0);
        if(not cnt) {
            ans[i] = true;
        } else if(f) {
            q1[h].push_back(i);
        } else {
            q2[h].push_back(i);
        }
    }

    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;
                if(q1.count(h)) {
                    for(auto x : q1[h]) {
                        ans[x] = true;
                    }
                    q1.erase(h);
                }
            }
        }
        if(q2.count(h)) {
            for(auto x : q2[h]) {
                ans[x] = true;
            }
            q2.erase(h);
        }
    }

    for(int i = 0; i < q; i ++ ) {
        std::cout << (ans[i] ? "Yes" : "No") << '\n';
    }

}

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

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

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3616kb

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
Runtime Error

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: