QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#630399#9356. LRU Algorithmcrimsonsunset#TL 0ms3652kbC++201.8kb2024-10-11 18:20:422024-10-11 18:20:44

Judging History

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

  • [2024-10-11 18:20:44]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3652kb
  • [2024-10-11 18:20:42]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops,inline,fast-math")

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;

//#define int long long
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

constexpr int mod = 1e9 + 4099, p = 6661;

void solve() {
    int n, q;
    cin >> n >> q;
    deque<int> a;
    vector<gp_hash_table<int, int>> fl(n + 1), pref(n + 1);
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (find(all(a), x) != a.end()) a.erase(find(all(a), x));
        a.push_front(x);
        int curhash = 0;
        for (int j = 1; j <= a.size(); ++j) {
            curhash = 1ll * curhash * p % mod;
            curhash += a[j - 1];
            if (curhash >= mod)
                curhash -= mod;
            pref[j][curhash] = 1;
        }
        fl[a.size()][curhash] = 1;
    }
    fl[0][0] = 1;
    pref[0][0] = 1;
    for (int i = 0; i < q; ++i) {
        int m;
        cin >> m;
        vector<int> x;
        int curhash = 0;
        for (int j = 0; j < m; ++j) {
            int lol;
            cin >> lol;
            if (lol) x.push_back(lol);
        }
        for (auto e : x) {
            curhash = 1ll * curhash * p % mod;
            curhash += e;
            if (curhash >= mod)
                curhash -= mod;
        }
        string ans = "No\n";
        if (x.size() == m) {
            if (pref[m][curhash]) ans = "Yes\n";
        }
        else {
            if (fl[x.size()][curhash]) ans = "Yes\n";
        }
        cout << ans;
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
        solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: