QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#181327#5256. Insertionsucup-team1209#WA 0ms3920kbC++209.2kb2023-09-16 17:46:192023-09-16 17:46:20

Judging History

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

  • [2023-09-16 17:46:20]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3920kb
  • [2023-09-16 17:46:19]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'