QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#630389 | #9356. LRU Algorithm | crimsonsunset# | TL | 1ms | 3576kb | C++20 | 1.7kb | 2024-10-11 18:16:10 | 2024-10-11 18:16:11 |
Judging History
answer
#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 long long mod = 1e9 + 4099, p = 6661;
void solve() {
int n, q;
cin >> n >> q;
vector<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_back(x);
reverse(all(a));
long long curhash = 0;
for (int j = 1; j <= a.size(); ++j) {
curhash *= p;
curhash += a[j - 1];
curhash %= mod;
pref[j][curhash] = 1;
}
fl[a.size()][curhash] = 1;
reverse(all(a));
}
fl[0][0] = 1;
pref[0][0] = 1;
for (int i = 0; i < q; ++i) {
int m;
cin >> m;
vector<int> x;
long long curhash = 0;
for (int j = 0; j < m; ++j) {
int lol;
cin >> lol;
if (lol) x.push_back(lol);
}
for (auto e : x) {
curhash *= p;
curhash += e;
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();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3576kb
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 ...