QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#549709#5440. P-P-PalindromeyueyueyWA 24ms264624kbC++142.8kb2024-09-06 19:58:432024-09-06 19:58:45

Judging History

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

  • [2024-09-06 19:58:45]
  • 评测
  • 测评结果:WA
  • 用时:24ms
  • 内存:264624kb
  • [2024-09-06 19:58:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define int long long
#define lowbit(x) (x&(-x))
#define pll pair<int,int>

const int N = 1e6+10;
const int mod =	998244353;
const ld eps = 1e-6;

int dx[] = {-1,1,0,0,-1,-1,1,1};
int dy[] = {0,0,-1,1,-1,1,-1,1};

int n,m;
int tr[N][28];
int fail[N],len[N],cnt[N];
int idx,last;
string s;

const int P1 = 998244353, BASE1 = 131;
const int P2 = 1000000007, BASE2 = 13331;
int B1[N],B2[N];
struct Hash{
    long long a1,a2;
    bool operator==(const Hash &b) const{
        return a1 == b.a1 && a2 == b.a2;
    }
    bool operator<(const Hash &b) const{
        return a1 == b.a1 ? a2 < b.a2 : a1 < b.a1;
    }
    Hash operator+(const int b) const{
        return { (a1 * BASE1 + b) % P1, (a2 *BASE2 + b) % P2 };
    }
    Hash operator<<(const int b) const{
        return { a1 * B1[b] % P1, a2 * B2[b] % P2 };
    }
    Hash operator-(const Hash &b) const{
        return { (a1 - b.a1 + P1) % P1, (a2 - b.a2 + P2) % P2 };
    }
}h[N],H[N];
Hash get(int l,int r){
    return h[r] - (h[l-1] << (r - l + 1));
}
map<Hash,int> ma;
void init(){
    memset(fail,0,sizeof(fail));
    memset(tr,0,sizeof(tr));
    memset(len,0,sizeof(len));
    memset(cnt,0,sizeof(cnt));
    fail[0] = 1; fail[1] = 0;
    len[0] = 0; len[1] = -1;
    idx = 1;
    B1[0] = 1;
    B2[0] = 1;
    for(int i=1;i<N;i++){
        B1[i] = 1ll * B1[i-1] * BASE1 % P1;
        B2[i] = 1ll * B2[i-1] * BASE2 % P2;
    }
}
int getfail(int x,int pos){
    while(pos-len[x]-1<=0||s[pos-len[x]-1]!=s[pos]) x = fail[x];
    return x;
}
void insert(char ch,int pos){
    int x = ch - 'a';
    int u = getfail(last,pos);
    if(!tr[u][x]){
        fail[++idx] = tr[getfail(fail[u],pos)][x];
        tr[u][x] = idx;
        len[idx] = len[u] + 2;
        int k = len[idx] - len[fail[idx]];
        Hash hash;
        if(len[idx]%k==0){
            hash = get(pos-k+1,pos);
            ma[hash] = max(ma[hash],len[idx]/k);
        }else{
            hash = h[len[idx]];
            ma[hash] = max(ma[hash],1ll);
        }
    }
    last = tr[u][x];
}
void solve(){
    cin>>n;
    init();
    for(int i=1;i<=n;i++){
        cin>>s;
        int siz = s.length();
        s = " " + s;
        last = 0;
        h[0].a1 = 0;
        h[0].a2 = 0;
        for(int j=1;j<=siz;j++) h[j] = h[j-1] + s[j];
        for(int j=1;j<=siz;j++){
            insert(s[j],j);
        }
    }
    int ans = 0;
    for(auto i : ma){
        ans += i.second * i.second;
    }
    cout<<ans<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int T = 1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*

/\_/\
(= ._.)
/ >  \>
*/

詳細信息

Test #1:

score: 100
Accepted
time: 12ms
memory: 264400kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 15ms
memory: 264624kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 19ms
memory: 263872kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: -100
Wrong Answer
time: 24ms
memory: 263536kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1281

result:

wrong answer 1st numbers differ - expected: '1282', found: '1281'