QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#105891#1964. Stock Price Predictionckiseki#WA 655ms39880kbC++204.0kb2023-05-15 20:36:072023-05-15 20:36:10

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-15 20:36:10]
  • 评测
  • 测评结果:WA
  • 用时:655ms
  • 内存:39880kb
  • [2023-05-15 20:36:07]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define orange(s...) orange_(#s, s)
#define debug(s...) debug_(#s, s)
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define orange(...) safe
#define debug(...) safe
#endif


namespace {

const int mod = 998244353;
const int base = 1203901;
const int maxn = 1 << 20;

struct Segtree {
    int wei[maxn];
    int sum[maxn * 2];
    int n;
    void build(int t_n) {
        n = 1;
        while (n < t_n) n *= 2;
        for (int i = 1; i < n * 2; i++)
            sum[i] = 0;
        for (int i = 1; i < n * 2; i++)
            wei[i] = 1;
    }
    void edit(int pos, int val, int val2) {
        pos += n;
        sum[pos] = val;
        wei[pos] = val2;
        while (pos >>= 1) {
            wei[pos] = 1LL * wei[pos << 1] * wei[pos << 1 | 1] % mod;

            sum[pos] = 
                (1LL * sum[pos << 1] * wei[pos << 1 | 1] + sum[pos << 1 | 1])
                    % mod;
        }
    }

    int getHash() {
        return sum[1];
    }

    void dump() {
        orange(sum + n, sum + n*2);
    }
} sgt, sgt2;

}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> m >> n;

    vector<int> a(m), b(n);
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
        cin >> b[i];

    vector<int> idx(m);
    {
        vector<pair<int,int>> u;
        for (int i = 0; i < m; i++) {
            u.emplace_back(a[i], i);
        }

        sort(u.begin(), u.end());

        for (int i = 0; i < m; i++) {
            idx[i] = u[i].second;
        }
    }


    vector<int> c(n);

    {
        vector<pair<int,int>> u;
        for (int i = 0; i < n; i++) {
            u.emplace_back(b[i], i);
        }

        sort(u.begin(), u.end());

        for (int i = 0; i < n; i++) {
            b[u[i].second] = i;
        }

        for (int i = 0, j = 0; i < n; i++) {
            if (i != 0 && u[i].first != u[i-1].first)
                ++j;
            c[u[i].second] = j;
        }

        orange(c.begin(), c.end());
    }

    safe;
    int H = 0;
    for (int i = 0; i < m; i++) {
        H = (1LL * H * base + idx[i]) % mod;
    }

    int C = 0;

    {
        map<int,int> mp;
        for (int i = 0; i < m; i++)
            mp[a[i]] += 1;
        for (auto [f, s]: mp) {
            C = (1LL * C * base + s) % mod;
        }
    }

    vector<int> ans;
    safe;

    sgt.build(n);
    sgt2.build(n);
    safe;

    vector<int> cnt(n);

    for (int i = 0; i < m; i++) {
        sgt.edit(b[i], i, base);
    }
    for (int i = 0; i < m; i++) {
        sgt2.edit(c[i], ++cnt[c[i]], base);
    }


    int hs = sgt.getHash();
    debug(hs, H);
        sgt2.dump();
    if (hs == H && sgt2.getHash() == C) {
        ans.emplace_back(0);
    }

    int tot = 0;
    for (int i=  0, prod = 1; i < m; i++) {
        tot = (tot + prod) % mod;
        prod = 1LL*prod*base % mod;
    }

    for (int i = m; i < n; i++) {
        sgt.edit(b[i - m], 0, 1);
        sgt.edit(b[i], i, base);

        --cnt[c[i - m]];
        sgt2.edit(c[i - m], cnt[c[i - m]], (cnt[c[i - m]] == 0 ? 1 : base));
        sgt2.edit(c[i], ++cnt[c[i]], base);

        H = (H + tot) % mod;
        debug(i - m);
        hs = sgt.getHash();
        debug(hs, H);
        sgt2.dump();
        debug(sgt2.getHash());
        if (hs == H && sgt2.getHash() == C) {
            ans.emplace_back(i - m + 1);
        }
    }

    debug(ans.size());

    if (ans.empty())
        cout << 0 << '\n';
    else
        for (size_t i = 0; i < ans.size(); i++)
            cout << ans[i] + 1 << (i+1==ans.size() ? '\n' : ' ');

    return 0;
}


詳細信息

Test #1:

score: 0
Wrong Answer
time: 655ms
memory: 39880kb

input:

10000 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

0

result:

wrong answer 1st lines differ - expected: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...997 989998 989999 990000 990001', found: '0'