QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#612581 | #4792. Origami | ucup-team4153# | WA | 119ms | 85616kb | C++20 | 2.3kb | 2024-10-05 12:08:08 | 2024-10-05 12:08:08 |
Judging History
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'