QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#578590#9356. LRU Algorithmpsycho#TL 1ms3776kbC++202.2kb2024-09-20 20:13:522024-09-20 20:13:53

Judging History

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

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

answer

#include <bits/stdc++.h>

using namespace std;

#define vc vector
#define pii pair <int, int>
//#define int long long
using ld = long double;
using ll = long long;
const int inf = 1e9;


template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
const int mod = 1e9 + 7;
const int P = 31;
const int N = 5000;
unordered_map<int, bool> th[N];
void solve_case() {
    int n, q; cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> arr(n, 0), narr;
    set<vector<int>> check;
    vector<vector<int>> xq(q);
    vector<bool> int_sz(n + 1);
    for (int iq = 0; iq < q; iq++) {
        int m; cin >> m;
        vector<int> x(m);
        for (int i = 0; i < m; i++) cin >> x[i];
        int_sz[m] = true;
        xq[iq] = x;
    }
    for (int i = 0; i < n; i++) {
        narr.clear();
        narr.push_back(a[i]);
        bool was = false;
        for (int j = 0; j < arr.size(); j++) {
            if (arr[j] == a[i]) {
                if (!was) {
                    was = true;
                } else {
                    narr.push_back(arr[j]);
                }
            } else {
                narr.push_back(arr[j]);
            }
        }
        arr = narr;
        int hash = 0;
        for (int len = 1; len <= n; len++) {
            hash = (1ll * hash * P + arr[len - 1]) % mod;
            if (int_sz[len]) {
                th[len][hash] = true;
            }
        }
    }
    for (int iq = 0; iq < q; iq++) {
        vector<int> x = xq[iq];
        int hash = 0;
        for (int i = 0; i < x.size(); i++) {
            hash = (1ll * hash * P + x[i]) % mod;
        }
        if (*max_element(x.begin(), x.end()) == 0 || th[x.size()][hash]) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    for (int i = 0; i <= n; i++) {
        th[i].clear();
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve_case();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: