QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#420098 | #5440. P-P-Palindrome | yiyiyi | WA | 13ms | 68068kb | C++17 | 2.4kb | 2024-05-24 14:39:30 | 2024-05-24 14:39:31 |
Judging History
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;
}
using ull = unsigned ll;
const ull base = 1e9+7;
ull powb[N];
int powb_n;
void init_powb(int n){
powb[0] = 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;
}
*/
/*
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};
*/
/**/
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: 67696kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 13ms
memory: 67548kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 3ms
memory: 67164kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: 0
Accepted
time: 9ms
memory: 68068kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1282
result:
ok 1 number(s): "1282"
Test #5:
score: -100
Wrong Answer
time: 10ms
memory: 66652kb
input:
5 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...
output:
15422
result:
wrong answer 1st numbers differ - expected: '3600000000', found: '15422'