QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#398087 | #5440. P-P-Palindrome | slenbol | WA | 1ms | 5816kb | C++14 | 1.8kb | 2024-04-24 22:06:04 | 2024-04-24 22:06:04 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template <typename T> inline void read(T &x)
{
x=0;T f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-')f=-1;
for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x*=f;
}
template <typename T,typename ...Args>void read(T &x,Args&...args){read(x),read(args...);}
template <typename T> void print(T x)
{
if(x<0) x=-x,putchar('-');
if(x>9) print(x/10);
putchar(x%10+48);
}
template <typename T> void print(T x,char c){print(x); putchar(c);}
template<typename T>inline void output(T x){print(x,' ');}
template<typename T,typename ...Arg>inline void output(T x,Arg ...arg){output(x);output(arg...);}
const int N=1000007;
int n; char s[N];
struct node
{
int ch[26],pa,d,top,len;
int& operator[](const int x)&{return ch[x];}
};
struct PAM
{
node S[N]; int idx,lst; ll ans;
map<pair<int,int>,int>cnt;
PAM(){idx=lst=2; S[1].pa=S[2].pa=1; S[1].len=-1;}
node& operator[](const int x)&{return S[x];}
int insert(int pos,int c,char *s)
{
int p=lst;
while(c^s[pos-S[p].len-1]) p=S[p].pa;
if(S[p][c]) return lst=S[p][c];
int np=lst=++idx,lnk=S[p].pa;
S[np].len=S[p].len+2;
while(c^s[pos-S[lnk].len-1]) lnk=S[lnk].pa;
S[S[p][c]=np].pa=S[lnk][c]?S[lnk][c]:2;
S[np].d=S[np].len-S[S[np].pa].len;
S[np].top=(S[np].d==S[S[np].pa].d)?S[S[np].pa].top:np;
return lst;
}
ll solve()
{
for(int i=3;i<=idx;i++)
{
if(S[i].len%S[i].d){ans++;continue;}
cnt[{S[i].d,S[i].top}]++;
}
for(auto [p,v]:cnt) ans+=(ll)v*v;
return ans;
}
}pam;
int main()
{
read(n);
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
int len=strlen(s+1);
s[0]=-1; pam.lst=2;
for(int j=1;j<=len;j++) s[j]-='a';
for(int j=1;j<=len;j++)
pam.insert(j,s[j],s);
}
print(pam.solve(),'\n');
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5684kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 5816kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1272
result:
wrong answer 1st numbers differ - expected: '1282', found: '1272'