QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#181327 | #5256. Insertions | ucup-team1209# | WA | 0ms | 3920kb | C++20 | 9.2kb | 2023-09-16 17:46:19 | 2023-09-16 17:46:20 |
Judging History
answer
#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using pi = pair <int, int> ;
using ll = long long;
cs int N = 1e5 + 5;
char S[N], T[N], P[N];
int n, m, k;
void work_skip(char *T, char *P, vector <bool> & mat) {
// mat[i] P[i, k] ~ T
string S = " " + string(T + 1) + string(P + 1);
int l = S.length() - 1;
vector <int> lcp(l + 1);
int mx = 1, pt = 1;
lcp[1] = l;
for(int i = 2; i <= l; i++) {
if(i <= mx) lcp[i] = min(lcp[i - pt + 1], mx - i + 1);
while(i + lcp[i] <= l && S[i + lcp[i]] == S[1 + lcp[i]]) ++ lcp[i];
if(i + lcp[i] - 1 > mx) pt = i, mx = i + lcp[i] - 1;
}
for(int i = 1; i <= k; i++) {
if(lcp[i + m] >= m) mat[i] = 1;
}
}
void work_mat(char *T, char *P, vector <bool> & mat) {
// mat[i] P[i, k] ~ T
string S = " " + string(T + 1) + string(P + 1);
int l = S.length() - 1;
vector <int> lcp(l + 1);
int mx = 1, pt = 1;
lcp[1] = l;
for(int i = 2; i <= l; i++) {
if(i <= mx) lcp[i] = min(lcp[i - pt + 1], mx - i + 1);
while(i + lcp[i] <= l && S[i + lcp[i]] == S[1 + lcp[i]]) ++ lcp[i];
if(i + lcp[i] - 1 > mx) pt = i, mx = i + lcp[i] - 1;
}
for(int i = 1; i <= k; i++) {
if(lcp[i + m] == k - i + 1) mat[i] = 1;
}
}
int run(char *T, char *P) {
vector <int> nxt(k + 1);
for(int i = 2, j = 0; i <= k; i++) {
while(j && P[j + 1] != P[i]) j = nxt[j];
if(P[j + 1] == P[i]) ++ j;
nxt[i] = j;
}
int ans = 0, p = 0;
for(int i = 1; i <= m; i++) {
while(p && T[i] != P[p + 1]) p = nxt[p];
if(T[i] == P[p + 1]) ++ p;
if(p == k) ++ ans, p = nxt[p];
}
return ans;
}
void work(char *S, char *T, char *P, vector <int> & ans, vector <bool> & mat, vector <int> & nxt, vector <int> & pnt) {
//mat[i] P [i, k] ~ T
vector <int> sum(k + 1);
for(int i = 2, j = 0; i <= k; i++) {
while(j && P[j + 1] != P[i]) j = nxt[j];
if(P[j + 1] == P[i]) ++ j;
nxt[i] = j;
}
for(int i = 1; i < k; i++) {
sum[i] = sum[nxt[i]];
if(i + m >= k) sum[i] += mat[i + 1];
}
int p = 0;
int fix = 0;
for(int i = 1; i <= n; i++) {
while(p && S[i] != P[p + 1]) p = nxt[p];
if(S[i] == P[p + 1]) ++ p;
if(p == k) {
++ fix;
p = nxt[p];
}
ans[i] += fix + sum[p];
pnt[i] = p;
}
}
void build_tree(vector <int> nxt, vector <int> & top, vector <int> & d) {
for(int i = 1; i <= k; i++) {
if(!nxt[i]) {
d[i] = i;
top[i] = 0;
}
if(nxt[i]) {
if(i - nxt[i] == d[nxt[i]]) {
d[i] = d[nxt[i]];
top[i] = top[nxt[i]];
}
else {
d[i] = i - nxt[i];
top[i] = nxt[i];
}
}
}
}
struct dat {
int l, r, d;
};
vector <dat> cat(int p, cs vector <int> & top, cs vector <int> & d) {
vector <dat> c;
while(p) {
int x = top[p];
c.pb({x + d[p], p, d[p]});
p = x;
}
return c;
}
void exgcd(int a, int b, int & x, int & y) {
if(!b) {
return x = 1, y = 0, void();
}
exgcd(b, a % b, y, x);
y -= a / b * x;
}
int pbpb(int s, int len1, int d1, int len2, int d2) {
// int l0 = 0, r0 = (len1 - 1) / d1 * d1;
// int l1 = 0, r1 = (len2 - 1) / d2 * d2;
// std::swap(l1 = s - l1, r1 = s - r1);
// int gcd = std::__gcd(d1, d2);
// ll lcm = d1 / gcd * (ll) d2;
// if(l0 % gcd != l1 % gcd) {
// return 0;
// }
// if(l1 < 0) {
// l1 %= d2;
// if(l1 < 0) l1 += d2;
// }
// {
// int u, v;
// exgcd(d1, d2, u, v);
// int w = len1 - len2;
// }
// if(l1) l1 = (l1 - 1) / lcm * lcm + lcm;
// r0 = min(r0, r1);
// if(r0 < l1) return 0;
// return 1 + (r0 - l1) / lcm;
len1 = (len1 - 1) / d1;
len2 = (len2 - 1) / d2;
int x = 0, y = 0;
// x * d1 + y * d2 == s
exgcd(d1, d2, x, y);
int d = __gcd(d1, d2);
// x * d1 + y * d2 == gcd(d1, d2) = d
if(s % d) return 0;
x *= s / d;
y *= s / d;
// assert(x * d1 + y * d2 == s);
// cerr << "FFFFFFF " << x << ' ' << y << ' ' << d1 << ' ' << d2 << ' ' << s << endl;
// cerr << len1 << ' ' << len2 << endl;
d1 /= d;
d2 /= d;
if(x < 0) {
int t = (-x) / d2;
x += t * d2;
y -= t * d1;
}
if(x < 0) {
x += d2;
y -= d1;
}
int t = x / d2;
x -= t * d2;
y += t * d1;
if(x < 0) return 0;
if(y < 0) return 0;
if(x > len1) return 0;
// cerr << "FFFFFFF " << x << ' ' << y << ' ' << d1 << ' ' << d2 << ' ' << s << endl;
// cerr << len1 << ' ' << len2 << endl;
int lp = 0;
if(y > len2) {
lp = (y - len2 - 1) / d1 + 1;
}
int rp = (len1 - x) / d2;
rp = min(rp, y / d1);
// cerr << lp << ' ' << rp << endl;
return max(0, rp - lp + 1);
// int ans = 0;
// while(1) {
// if(y < 0) break;
// if(x > len1) break;
// if(y <= len2) ++ ans;
// x += d2;
// y -= d1;
// }
// return ans;
}
int fuck(dat a, dat b) {
auto [l1, r1, d1] = a;
auto [l2, r2, d2] = b;
int len1 = r1 - l1 + 1;
int len2 = r2 - l2 + 1;
int ans = 0;
int s = k - m - l1 - l2;
// for(int i = 0; i < len1; i += d1)
// for(int j = 0; j < len2; j += d2) {
// if(i + j == s) ++ ans; // , cout <<i << ' ' <<j <<endl;
// }
// if(ans != pbpb(s, len1, d1, len2, d2)) {
// cout << s << ' '<< len1 << ' ' << d1 << ' ' << len2 << ' ' << d2 << ' ' << ans << endl;
// cout << pbpb(s, len1, d1, len2, d2) << '\n';
// assert(0);
// }
return pbpb(s, len1, d1, len2, d2);
}
int calc(int p1, int p2, cs vector <int> & top1, cs vector <int> & d1, cs vector <int> & top2, cs vector <int> & d2) {
vector <dat> c1 = cat(p1, top1, d1);
vector <dat> c2 = cat(p2, top2, d2);
int ans = 0;
for(auto a : c1) for(auto b : c2) ans += fuck(a, b);
return ans;
}
void skip(vector <int> & ans, vector <int> t2, vector <int> pnt) {
vector <bool> mat(k + 1);
work_skip(T, P, mat);
vector <int> nxt(k + 1);
for(int i = 2, j = 0; i <= k; i++) {
while(j && P[j + 1] != P[i]) j = nxt[j];
if(P[j + 1] == P[i]) ++ j;
nxt[i] = j;
}
vector <int> t1(k + 1);
for(int i = 1; i <= k; i++) {
if(!mat[nxt[i] + 1]) {
t1[i] = t1[nxt[i]];
}
else {
t1[i] = nxt[i];
}
}
vector <int> top1(k + 1), d1(k + 1);
vector <int> top2(k + 1), d2(k + 1);
build_tree(t1, top1, d1);
build_tree(t2, top2, d2);
int p = 0;
for(int i = 1; i < n; i++) {
while(p && S[i] != P[p + 1]) p = nxt[p];
if(S[i] == P[p + 1]) ++ p;
if(p == k) {
p = nxt[p];
}
int fucku = mat[p + 1] ? p : t1[p];
// cout << "FFdsafasfasdfasfd " << i << ' ' << fucku <<' ' << pnt[n - i] << endl;
ans[i] += calc(fucku, pnt[n - i], top1, d1, top2, d2);
}
}
void output(vector <int> ans) {
int mx = 0, cnt = 0;
int lp = n, rp = 0;
for(int i = 1; i <= n; i++) {
if(ans[i] > mx) {
mx = ans[i];
cnt = 1;
}
else if(ans[i] == mx) {
cnt ++;
}
}
for(int i = 1; i <= n; i++)
if(ans[i] == mx) {
lp = min(lp, i);
rp = max(rp, i);
}
// for(int i = 0; i <= n; i++)
// cout << ans[i] << ' ';
// cout << endl;
cout << mx << ' ' << cnt << ' ' << lp << ' ' << rp << '\n';
}
void Main() {
scanf("%s%s%s", S + 1, T + 1, P + 1);
n = strlen(S + 1);
m = strlen(T + 1);
k = strlen(P + 1);
vector <int> nxt(k + 1);
vector <int> pnt(n + 1);
vector <int> ans1(n + 1);
vector <bool> mat1(k + 1);
work_mat(T, P, mat1);
work(S, T, P, ans1, mat1, nxt, pnt);
// for(int x : ans1) cout << x << ' '; cout << endl;
reverse(S + 1, S + n + 1);
reverse(T + 1, T + m + 1);
reverse(P + 1, P + k + 1);
vector <int> ans2(n + 1);
vector <bool> mat2(k + 1);
work_mat(T, P, mat2);
work(S, T, P, ans2, mat2, nxt, pnt);
// for(int x : ans2) cout << x << ' '; cout << endl;
reverse(S + 1, S + n + 1);
reverse(T + 1, T + m + 1);
reverse(P + 1, P + k + 1);
vector <int> ans(n + 1);
for(int i = 0; i <= n; i++)
ans[i] = ans1[i] + ans2[n - i];
int bonus = run(T, P);
// cout << "FFF " << bonus << endl;
for(int i = 0; i <= n; i++)
ans[i] += bonus;
if(m >= k) {
output(ans);
return;
}
vector <int> ans3(n + 1);
skip(ans3, nxt, pnt);
// for(int x : ans3) cout << x << ' '; cout << endl;
for(int i = 0; i <= n; i++)
ans[i] += ans3[i];
output(ans);
}
int main() {
#ifdef zqj
freopen("1.in","r",stdin);
#endif
Main();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3920kb
input:
rrddrrrdd ddrrd rrddrr
output:
2 2 6 7
result:
ok 4 number(s): "2 2 6 7"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3648kb
input:
z zzkkzzkk z
output:
5 1 1 1
result:
wrong answer 2nd numbers differ - expected: '2', found: '1'