Hack #912 - QOJ.ac

ID	提交记录ID	题目	Hacker	Owner	结果	提交时间	测评时间
#912	#584002	#9356. LRU Algorithm	ship2077	kevinshan	Success!	2024-09-26 19:12:39	2024-09-26 19:12:39

详细

Extra Test:

Wrong Answer

time: 2ms

memory: 5908kb

input:

1
5000 1
1233 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5...

output:

Yes

result:

wrong answer 1st lines differ - expected: 'No', found: 'Yes'

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#584002	#9356. LRU Algorithm	kevinshan^#	WA	235ms	6200kb	C++14	1.8kb	2024-09-23 03:02:33	2024-10-14 07:31:07

answer

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int BK = 100003;
const ull MOD = (1ll << 61) - 1;
const int BASE = 1445;
const int N = 5010;
int Case, n, q;
vector<pair<ull, int>> g[BK];
int a[N];
inline ull Mul(ull a, ull b) {
    return (__int128)a * b % MOD;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> Case;
    while (Case--) {
        cin >> n >> q;
        vector<int> clr;
        vector<bool> ans(q + 1);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1, k, x; i <= q; ++i) {
            cin >> k;
            int bkid = 0;
            ull hs = 0;
            for (int j = 1, x, la = -1; j <= k; ++j) {
                cin >> x;
                if (x || la) {
                    bkid = (1ll * bkid * BASE + x + 1) % BK;
                    hs = (Mul(hs, BASE) + x + 1) % MOD;
                }
                la = x;
            }
            if (bkid == 1 && hs == 1) ans[i] = 1;
            g[bkid].push_back({hs, i});
            clr.push_back(bkid);
        }
        vector<int> buf(1, 0);
        for (int t = 1; t <= n; ++t) {
            auto it = find(buf.begin(), buf.end(), a[t]);
            if (it == buf.end()) { buf.insert(buf.begin(), a[t]); }
            else { buf.erase(it); buf.insert(buf.begin(), a[t]); }
            int bkid = 0;
            ull hs = 0;
            for (auto x : buf) {
                bkid = (1ll * bkid * BASE + x + 1) % BK;
                hs = (Mul(hs, BASE) + x + 1) % MOD;
                for (auto [hsval, id] : g[bkid]) if (hsval == hs) ans[id] = 1;
            }
        } 
        for (int i = 1; i <= q; ++i) cout << (ans[i] ? "Yes" : "No") << '\n';
        for (auto x : clr) g[x].clear();
    }
    return 0;
}

源文件, 语言: C++14