QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#420117#5440. P-P-PalindromeyiyiyiWA 13ms68564kbC++172.3kb2024-05-24 14:44:432024-05-24 14:44:43

Judging History

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

  • [2024-05-24 14:44:43]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:68564kb
  • [2024-05-24 14:44:43]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rev_rep(i,s,t) for(int i=(s);i>=(t);i--)
using namespace std;
ll ci(){ ll x; scanf("%lld", &x); return x; }

enum{N = 1000023};

struct sth{ int l,r,x; };

vector<sth>vec;

struct node{
	node*fa;
	int len;
	map<char,node*> c;
}d[N];
int tot_d = 1;
node* last = d;
char str[N],now_pos;
void init_PAM(){
	d[0]=(node){d+1,0};
	d[1]=(node){d,-1};
}
node* extend(int x){
	str[++now_pos] = x;
	node*p = last;
	for(; str[now_pos-p->len-1]!=x; p=p->fa);
	if( p->c[x]==0 ){
		node*e = &d[++tot_d];
		node*q = p->fa;
		for(; str[now_pos-q->len-1]!=x; q=q->fa);
		*e = (node){ q->c[x]==0 ? d:q->c[x] ,p->len+2};
		int lena = e->len, lenb = e->fa->len;
		if( lenb ) vec.push_back(sth{now_pos-lena+1, now_pos, lena-lenb});
		p->c[x] = e;
	}
	last = p->c[x];
	return last;
}

const int mod = 1e9+9;
using ull = pair<unsigned ll, ll>;
ull operator*(const ull&a, const ull&b){
	return {a.first*b.first, (a.second*b.second)%mod};
}
ull operator+(const ull&a, const int x){
	return {a.first+x, (a.second+x)%mod};
}
ull operator-(const ull&a, const ull&b){
	return {a.first-b.first, (a.second-b.second+mod)%mod};
}
const ull base = {1e9+7, 19260817};
ull powb[N];
int powb_n;
void init_powb(int n){
	powb[0] = {1,1};
	rep(i,powb_n+1,n) powb[i]=powb[i-1]*base;
	powb_n = max(powb_n,n);
}
class HASH{
private:
	ull a[N];
public:
	void init(int n,char*s){
		init_powb(n);
		rep(i,1,n) a[i]=a[i-1]*base+s[i];
	}
	ull query(int l,int r){
		return a[r]-(a[l-1]*powb[r-l+1]);
	}
};
/*
int LCP(HASH&h, int i, int j, int n){
	int l=0, r=min(n-i+1, n-j+1);
	while( l<r ){
		int w = (l+r+1)/2;
		if( h.query(i, i+w-1) == h.query(j, j+w-1) ) l=w;
		else r = w-1;
	} return l;
}
*/
/**/

HASH h;

char s[N];

signed main(){
	init_PAM();
	int n = ci();
	rep(i,1,n){
		scanf("%s", s+1);
		int m = strlen(s+1);
		rep(i,1,m) extend(s[i]);
		extend('#');
		extend('$');
	}

	h.init(now_pos, str);

	//puts(str+1);
	int ans = 0;
	for(auto e:vec){
		auto [l,r,x] = e;
		if( (r-l+1)%x==0 && h.query(l,r-x) == h.query(l+x,r) ){
		//printf("%d %d %d\n", l,r,x);
			ans += (r-l+1)/x-1;
		}
	}
	ans *= 2;
	ans += tot_d - 3;
	
	printf("%lld\n", ans);

	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 11ms
memory: 68264kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 8ms
memory: 67896kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 4ms
memory: 67500kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: 0
Accepted
time: 4ms
memory: 67984kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1282

result:

ok 1 number(s): "1282"

Test #5:

score: -100
Wrong Answer
time: 13ms
memory: 68564kb

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

16129

result:

wrong answer 1st numbers differ - expected: '3600000000', found: '16129'