QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#571603 | #9356. LRU Algorithm | real_sigma_team# | RE | 0ms | 3580kb | C++17 | 1.7kb | 2024-09-18 01:18:55 | 2024-09-18 01:19:00 |
Judging History
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 ...