QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398087#5440. P-P-PalindromeslenbolWA 1ms5816kbC++141.8kb2024-04-24 22:06:042024-04-24 22:06:04

Judging History

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

  • [2024-04-24 22:06:04]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5816kb
  • [2024-04-24 22:06:04]
  • 提交

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'