QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#105891 | #1964. Stock Price Prediction | ckiseki# | WA | 655ms | 39880kb | C++20 | 4.0kb | 2023-05-15 20:36:07 | 2023-05-15 20:36:10 |
Judging History
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'