QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#571603#9356. LRU Algorithmreal_sigma_team#RE 0ms3580kbC++171.7kb2024-09-18 01:18:552024-09-18 01:19:00

Judging History

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

  • [2024-09-26 19:14:31]
  • hack成功,自动添加数据
  • (/hack/913)
  • [2024-09-26 19:12:47]
  • hack成功,自动添加数据
  • (/hack/912)
  • [2024-09-18 01:19:00]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3580kb
  • [2024-09-18 01:18:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    cin >> tests;
    while (tests--) {
        int n, q;
        cin >> n >> q;
        vector<int> a(n, 0);
        vector<vector<int>> b;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            int k = find(a.begin(), a.end(), x) - a.begin();
            if (k < a.size()) {
                a.erase(a.begin() + k);
            } else {
                a.pop_back();
            }
            a.insert(a.begin(), x);
            b.push_back(a);
        }
        vector<int> p(n);
        iota(p.begin(), p.end(), 0);
        for (int i = n - 1; i >= 0; --i) {
            vector<int> cnt(n + 1);
            for (int j = 0; j < n; ++j) {
                cnt[b[j][i]]++;
            }
            for (int j = 1; j <= n; ++j) cnt[j] += cnt[j - 1];
            vector<int> pn(n);
            for (int j = n - 1; j >= 0; --j) {
                pn[--cnt[b[p[j]][i]]] = p[j];
            }
            swap(p, pn);
        }
        while (q--) {
            int m;
            cin >> m;
            vector<int> x(m);
            for (auto& i : x) cin >> i;
            while (x.back() == 0) x.pop_back();
            int L = 0, R = n - 1;
            while (L != R) {
                int M = (L + R) / 2 + 1;
                if (vector(b[p[M]].begin(), b[p[M]].begin() + x.size()) <= x) L = M;
                else R = M - 1;
            }
            if (vector(b[p[L]].begin(), b[p[L]].begin() + x.size()) == x) cout << "Yes\n";
            else cout << "No\n";
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: