QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#612581#4792. Origamiucup-team4153#WA 119ms85616kbC++202.3kb2024-10-05 12:08:082024-10-05 12:08:08

Judging History

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

  • [2024-10-05 12:08:08]
  • 评测
  • 测评结果:WA
  • 用时:119ms
  • 内存:85616kb
  • [2024-10-05 12:08:08]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;using ld=long double;using ll=long long;
using pll=pair<ll,ll>;
const int M=1e9+7,N=5e3+10,inv2=(M+1)/2,P=20;const ld eps=1e-8,pi=acos(-1);
ll poww(ll bs,ll x){ll res=1;for(;x;x>>=1,(bs*=bs)%=M)if(x&1)(res*=bs)%=M;return res;}
ll invv(ll bs){return poww(bs,M-2);}
struct Mana
{
    int len,mr,C,mxLen;vector<int>s,mxp;
    void Pre(vector<int>&_s,vector<int>&d)
    {
        //cout<<"!!\n";
        s.push_back(-1);mr=-1;for(auto&k:_s)s.push_back(k),s.push_back(-1);
        //for(auto&k:s)cout<<k<<"|";cout<<'\n';
        mxLen=1;len=s.size();mxp.assign(len+1,0);
        for(int x=1;x<len-1;x++){
            if(mr>x)mxp[x]=min(mr-x,mxp[C-x]);int bord=min(x,len-x-1);
            while(mxp[x]<bord&&s[x-mxp[x]-1]==s[x+mxp[x]+1])mxp[x]++;if(x+mxp[x]>mr)mr=x+mxp[x],C=x*2;
        }
        //for(int i=1;i<len-1;i++)cout<<mxp[i]<<"*";cout<<'\n';
        //vector<int>res(len,1);
        for(int i=0;i<len;i+=2)
        {
            d[i/2]&=(i-mxp[i]==0||i+mxp[i]==len-1);
           // cout<<res[i]<<".\n"[i==len-2];
        }
        //return res;
    }
};
struct S
{
    int n,m;ll res=1;
    vector<vector<int>>mat;
    void ini()
    {
        cin>>n>>m;mat.resize(n,vector<int>(m));
        for(auto&k:mat)
        {
            string s;cin>>s;for(int i=0;i<m;i++)k[i]=s[i]-'a';
        }
        sol();
        swap(n,m);
        vector<vector<int>>mat2(n,vector<int>(m));
        for(int i=0;i<n;i++)for(int j=0;j<m;j++)mat2[i][j]=mat[j][i];
        swap(mat,mat2);
        sol();cout<<res<<'\n';
    }
    void sol()
    {
        vector<int>div(m+1,1);
        for(int i=0;i<n;i++)
        {
            Mana A;A.Pre(mat[i],div);
        }
        //for(int i=0;i<=m;i++)cout<<div[i];cout<<'\n';
        ll cc=0;map<int,int>mp;
        for(int i=1,l=0;i<=m;i++)if(div[i]==1)cc++,mp[i-l]++,l=i;
        auto ite=--mp.end();ll csp=(*ite).second;
        //cout<<cc<<"&"<<csp<<'\n';
        ll A=ll(cc)*(cc+1)/2-(cc-csp);
        res*=A;
    }
    void solve()
    {

    }
};
void precal()
{

}
signed main()
{
    cout<<fixed<<setprecision(12);
    ios::sync_with_stdio(0);
    cin.tie(0);
    precal();
    int t=1;//cin>>t;
    while(t--){S SS;SS.ini();SS.solve();}
}
/*
2 3
aba
aba
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3536kb

input:

5 7
baabbaa
cbbccbb
ababbab
cabccba
bccaacc

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 119ms
memory: 85616kb

input:

1000000 1
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
...

output:

500000500000

result:

ok 1 number(s): "500000500000"

Test #3:

score: 0
Accepted
time: 24ms
memory: 11152kb

input:

1000 1000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

250500250000

result:

ok 1 number(s): "250500250000"

Test #4:

score: 0
Accepted
time: 39ms
memory: 11024kb

input:

1000 1000
abaaabababbbbababbabbbaabababbaaabbbbabbabaaababaaabbaabbabaabababbbabaaababbbbaaabaabbbbaaaaabababbbababaaababbaaaaaaabbbbbbbaaababaabaabbbbbbabbaaabbbbaaabbaababaababaaaaaaabaabbabbbbbabaabbbbbbabbabaaaaaaababbbaabaabbbbbabbabbababaabaababbbaaaaaaaabbbbbbaaaaaabaabaabaabbbbbbaabbaabaabab...

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3496kb

input:

26 30
yyepjjjjpeyffyyffyyffffffffyyf
yyepjjjjpeyffyyffyyffffffffyyf
yyepjjjjpeyffyyffyyffffffffyyf
ddjuooooujdkkddkkddkkkkkkkkddk
ddjuooooujdkkddkkddkkkkkkkkddk
yyepjjjjpeyffyyffyyffffffffyyf
yyepjjjjpeyffyyffyyffffffffyyf
yyepjjjjpeyffyyffyyffffffffyyf
yyepjjjjpeyffyyffyyffffffffyyf
ddjuooooujdkkdd...

output:

77

result:

wrong answer 1st numbers differ - expected: '3800', found: '77'