QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#198843#5440. P-P-PalindromeUrgantTeamWA 1257ms92284kbC++232.9kb2023-10-03 17:43:562023-10-03 17:43:58

Judging History

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

  • [2023-10-03 17:43:58]
  • 评测
  • 测评结果:WA
  • 用时:1257ms
  • 内存:92284kb
  • [2023-10-03 17:43:56]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
ll mod = 1e9 + 7, P = 29;
int const maxn = 1e6 + 5;
ll p[maxn], rev[maxn], h[maxn];
vector < pair < int, int > > palindromes;
int len[maxn];
map < ll, int > used;
vector < ll > open[maxn];

ll st(ll x, ll y) {
    if (y == 0) return 1;
    if (y % 2 == 0) return st(x * x % mod, y / 2);
    return x * st(x, y - 1) % mod;
}

inline ll get(int l, int r) {
    return (h[r] - h[l - 1] + mod) * rev[l - 1] % mod;
}

void manaker_odd(string s) {
    int l = 0, r = 0, n = s.size();
    for (int i = 1; i < n; i++) {
        if (i <= r) len[i] = min(r - i + 1, len[l + r - i]);
        else len[i] = 0;
        while (i - len[i] > 0 && i + len[i] < n && s[i - len[i]] == s[i + len[i]]) {
            palindromes.push_back({i - len[i], i + len[i]});
            len[i]++;
        }
        if (i + len[i] - 1 > r) {
            r = i + len[i] - 1;
            l = i - len[i] + 1;
        }
    }
}

void manaker_even(string s) {
    int l = 0, r = 0, n = s.size();
    for (int i = 2; i < n; i++) {
        if (i <= r) len[i] = min(r - i + 1, len[l + r - i]);
        else len[i] = 0;
        while (i - len[i] - 1 > 0 && i + len[i] < n && s[i - len[i] - 1] == s[i + len[i]]) {
            palindromes.push_back({i - len[i] - 1, i + len[i]});
            len[i]++;
        }
        if (i + len[i] - 1 > r) {
            r = i + len[i] - 1;
            l = i - len[i];
        }
    }
}

main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
#endif // HOME
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    p[0] = 1, rev[0] = 1;
    for (int i = 1; i < maxn; i++) p[i] = p[i - 1] * P % mod;
    rev[maxn - 1] = st(p[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 1; i--) rev[i] = rev[i + 1] * P % mod;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        int len = s.size();
        s = "#" + s;
        for (int j = 1; j <= len; j++) {
            h[j] = (h[j - 1] + (s[j] - 'a' + 1) * p[j - 1]) % mod;
        }
        palindromes = {};
        manaker_even(s);
        manaker_odd(s);
        for (auto key : palindromes) used[get(key.first, key.second)] = key.second - key.first + 1;
    }
    for (auto key : used) {
        open[key.second].push_back(key.first);
    }
    set < ll > bad;
    ll ans = 0;
    for (int len = 1; len < maxn; len++) {
        for (auto key : open[len]) {
            if (bad.find(key) != bad.end()) continue;
            int cur_len = 0;
            ll cur_h = 0;
            while (1) {
                cur_h = (cur_h * p[len] + key) % mod;
                if (used.find(cur_h) == used.end()) break;
                cur_len += len;
                bad.insert(cur_h);
            }
            ll cnt = cur_len / len;
            ans += cnt * cnt;
        }
    }
    cout << ans << '\n';
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 15ms
memory: 46080kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 22ms
memory: 48148kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 22ms
memory: 48084kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: 0
Accepted
time: 22ms
memory: 48124kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1282

result:

ok 1 number(s): "1282"

Test #5:

score: 0
Accepted
time: 176ms
memory: 57624kb

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #6:

score: 0
Accepted
time: 176ms
memory: 55584kb

input:

5
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #7:

score: -100
Wrong Answer
time: 1257ms
memory: 92284kb

input:

3
abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...

output:

310146

result:

wrong answer 1st numbers differ - expected: '133586', found: '310146'