QOJ.ac

QOJ

ID	提交记录ID	题目	Hacker	Owner	结果	提交时间	测评时间
#913	#578617	#9356. LRU Algorithm	ship2077	psycho	Success!	2024-09-26 19:14:22	2024-09-26 19:14:23

詳細信息

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	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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();
}

源文件, 语言: C++20