QOJ.ac

QOJ

ID	Submission ID	Problem	Hacker	Owner	Result	Submit time	Judge time
#913	#578617	#9356. LRU Algorithm	ship2077	psycho	Success!	2024-09-26 19:14:22	2024-09-26 19:14:23

Details

Extra Test:

Wrong Answer

time: 158ms

memory: 3664kb

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
#578617	#9356. LRU Algorithm	psycho^#	WA	369ms	33880kb	C++20	2.8kb	2024-09-20 20:26:17	2024-10-14 07:31:06

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 = 5002;
vector<int> vec[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<int> 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] += 1;
        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]) {
                vec[len].push_back(hash);
            }
        }
    }
    // 1e7 information
    for (int x = 1; x <= n; x++) {
        if (int_sz[x] >= 3) {
            sort(vec[x].begin(), vec[x].end());
        }
    }
    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) {
            cout << "Yes\n";
            continue;
        }
        int m = x.size();
        bool ok = false;
        if (int_sz[m] >= 3) {
            ok |= binary_search(vec[m].begin(), vec[m].end(), hash);
        } else {
            for (int xh : vec[m]) {
                if (xh == hash) {
                    ok = true;
                }
            }
        }
        if (ok) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    for (int i = 0; i <= n; i++) {
        vec[i].clear();
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve_case();
}

Source code, Language: C++20