Hack #912 - QOJ.ac

ID	Submission ID	Problem	Hacker	Owner	Result	Submit time	Judge time
#912	#584002	#9356. LRU Algorithm	ship2077	kevinshan	Success!	2024-09-26 19:12:39	2024-09-26 19:12:39

Details

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	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#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;
}

Source code, Language: C++14