QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#578590 | #9356. LRU Algorithm | psycho# | TL | 1ms | 3776kb | C++20 | 2.2kb | 2024-09-20 20:13:52 | 2024-09-20 20:13:53 |
Judging History
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 ...