QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#80034#5440. P-P-PalindromeAPJifengcWA 2ms14000kbC++202.4kb2023-02-21 20:08:582023-02-21 20:09:13

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-21 20:09:13]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:14000kb
  • [2023-02-21 20:08:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int n;
char s[MAXN];
const int P1 = 993244853, BASE1 = 131;
const int P2 = 1000000009, BASE2 = 13331;
int B1[MAXN], B2[MAXN];
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[MAXN];
Hash split(int l, int r) {
    return h[r] - (h[l - 1] << (r - l + 1));
}
map<Hash, int> cnt;
struct PalindromeAutomaton {
    int t[MAXN][26], len[MAXN], fail[MAXN];
    int lst, tot;
    PalindromeAutomaton() {
        len[1] = -1, fail[0] = 1;
        lst = tot = 1;
    }
    void insert(int c, int i) {
        int p = lst;
        while (s[i - len[p] - 1] != s[i]) p = fail[p];
        if (!t[p][c]) {
            ++tot;
            int q = fail[p];
            while (s[i - len[q] - 1] != s[i]) q = fail[q];
            fail[tot] = t[q][c];
            len[tot] = len[p] + 2;
            t[p][c] = tot;
            int diff = len[tot] - len[fail[tot]];
            int l = (len[tot] % diff == 0 ? diff : len[tot]);
            // printf("l = %d\n", l);
            cnt[split(i - l + 1, i)] = max(cnt[split(i - l + 1, i)], len[tot] / l);
        }
        lst = t[p][c];
    }
} pam;
int main() {
    scanf("%d", &n);
    B1[0] = 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;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%s", s + 1);
        int m = strlen(s + 1);
        for (int j = 1; j <= m; j++) {
            h[j] = h[j - 1] + (s[j] - 'a' + 1);
        }
        pam.lst = 0;
        for (int j = 1; j <= m; j++) {
            pam.insert(s[j] - 'a', j);
        }
    }
    long long ans = 0;
    for (auto p : cnt) {
        // printf("(%lld, %lld): %d\n", p.first.a1, p.first.a2, p.second);
        ans += 1ll * p.second * p.second;
    }
    printf("%lld\n", ans);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 13800kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 1ms
memory: 13788kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 0ms
memory: 14000kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 13884kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1286

result:

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