QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#628251#7780. Dark LaTeX vs. Light LaTeXStelorWA 451ms276428kbC++202.3kb2024-10-10 19:19:462024-10-10 19:19:47

Judging History

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

  • [2024-11-25 20:53:52]
  • hack成功,自动添加数据
  • (/hack/1258)
  • [2024-10-10 19:19:47]
  • 评测
  • 测评结果:WA
  • 用时:451ms
  • 内存:276428kb
  • [2024-10-10 19:19:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
typedef pair<ll,PII> PIII;
#define x first
#define y second
const ll N =1e5+100,M=1e6+100,INF = 1e18;
ll n,m;
ll P = 1312931;
ll mod= 10000079;
ll hs[N],ht[N],p[N];
string s,t;
ll ans=0;
int f[5005][5005],g[5005][5005];
ll sum1[5005],sum2[5005];
ll cnt[10012500];
void init(){
    for(ll i=n+1;i>=1;i--){
        for(ll j=n+1;j>=1;j--){
            f[i][j]=0;
        }
    }
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            g[i][j]=0;
        }
    }
    for(ll i=n;i>=1;i--){
        for(ll j=n;j>=1;j--){
            if(s[i]==s[j]) f[i][j]=f[i+1][j+1]+1;
        }
    }
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            if(s[i]==t[j]) g[i][j]=g[i-1][j-1]+1;
        }
    }
}
void clear(){
    for(ll i=0;i<=m+10;i++) sum1[i]=sum2[i]=0;
}
void work(){
    init();
    for(ll i=3;i<=n;i++){//r
        clear();
        for(ll j=1;j<=m;j++){
            sum1[g[i-1][j]]++;
            sum2[g[i-1][j]]+=g[i-1][j];
        }
        for(ll j=m;j>=1;j--) sum1[j]+=sum1[j+1],sum2[j]+=sum2[j+1];
        for(ll j=1;j<=i-2;j++){//l
            ll len=i-1-j+1;
            ll l=max((ll)1,len-f[i][j]);
            ll r=len-1;
            if(l>r) continue;
            ans+=sum1[r+1]*(r-l+1);
            ans+=sum2[l]-sum2[r+1]-(sum1[l]-sum1[r+1])*(l-1);
        }
    }
}
void solve(){
    cin>>s;
    cin>>t;
    s='?'+s,t='?'+t;
    n=s.length()-1,m=t.length()-1;
    for(ll i=1;i<=n;i++) hs[i]=(hs[i-1]*P+s[i])%mod;
    for(ll i=1;i<=m;i++) ht[i]=(ht[i-1]*P+t[i])%mod;
    map<ll,ll> mp;
    for(ll i=1;i<=n;i++){
        for(ll j=i;j<=n;j++){
            ll x=(hs[j]%mod-hs[i-1]*p[j-i+1]%mod+mod)%mod;
            cnt[x]++;
        }
    }
    for(ll i=1;i<=m;i++){
        for(ll j=i;j<=m;j++){
            ll x=(ht[j]%mod-ht[i-1]*p[j-i+1]%mod+mod)%mod;
            ans+=cnt[x];
        }
    }
    work();
    swap(s,t);
    n=s.length()-1,m=t.length()-1;
    work();
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    p[0]=1;
    for(ll i=1;i<=5005;i++){
        p[i]=p[i-1]*P%mod;
    }
    ll __=1;//cin>>__;
    while(__--) solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 18184kb

input:

abab
ab

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: 0
Accepted
time: 0ms
memory: 19888kb

input:

abab
abaaab

output:

29

result:

ok 1 number(s): "29"

Test #3:

score: 0
Accepted
time: 0ms
memory: 20004kb

input:

abcd
abcde

output:

10

result:

ok 1 number(s): "10"

Test #4:

score: 0
Accepted
time: 3ms
memory: 20004kb

input:

aaba
ba

output:

6

result:

ok 1 number(s): "6"

Test #5:

score: 0
Accepted
time: 0ms
memory: 89588kb

input:

babababaaabbaabababbbaabbbababbaaaaa
aaaabbaababbab

output:

1161

result:

ok 1 number(s): "1161"

Test #6:

score: 0
Accepted
time: 451ms
memory: 276428kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

78156256250000

result:

ok 1 number(s): "78156256250000"

Test #7:

score: -100
Wrong Answer
time: 23ms
memory: 121964kb

input:

gzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggz...

output:

60736415

result:

wrong answer 1st numbers differ - expected: '60716448', found: '60736415'