oj.uz

답안 #83797

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
83797 2018-11-10T17:14:23 Z popovicirobert 회문 (APIO14_palindrome) C++14
73 / 100
 1000 ms 80756 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MAXN = (int) 3e5;
const int B = 53;
const int LOG = 19;

char str[MAXN + 1];

struct Data {
    int val1, val2;
    int pos;
    bool operator <(const Data &other) const {
        if(val1 == other.val1)
            return val2 < other.val2;
        return val1 < other.val1;
    }
}aux[MAXN + 1];

int P[MAXN + 1][LOG + 1], fr[26], lg;
int rmq[MAXN + 1][LOG + 1];
int ord[MAXN + 1], where[MAXN + 1];
char Log[MAXN + 1];

bool cmp(int a, int b) {
    return P[a][lg] < P[b][lg];
}

inline void suffix_array(int n) {
    int i;
    for(i = 1; i <= n; i++) {
        fr[str[i] - 'a']++;
    }
    for(i = 1; i < 26; i++) {
        fr[i] += fr[i - 1];
    }
    for(i = 1; i <= n; i++) {
        P[i][0] = fr[str[i] - 'a'];
    }
    for(lg = 1; (1 << lg) <= 2 * n; lg++) {
        for(i = 1; i <= n; i++) {
            if(i + (1 << (lg - 1)) <= n) {
                aux[i] = {P[i][lg - 1], P[i + (1 << (lg - 1))][lg - 1], i};
            }
            else {
                aux[i] = {P[i][lg - 1], 0, i};
            }
        }
        sort(aux + 1, aux + n + 1);
        int cur = 0;
        for(i = 1; i <= n; i++) {
            if(aux[i].val1 != aux[i - 1].val1 || aux[i].val2 != aux[i - 1].val2) {
                cur++;
            }
            P[aux[i].pos][lg] = cur;
        }
    }
    lg--;
    for(i = 1; i <= n; i++) {
        ord[i] = i;
    }
    sort(ord + 1, ord + n + 1, cmp);
    for(i = 1; i <= n; i++) {
        where[ord[i]] = i;
    }
    for(i = 1; i < n; i++) {
        int a = ord[i], b = ord[i + 1];
        for(int bit = lg; bit >= 0; bit--) {
            if(a + (1 << bit) <= n + 1 && b + (1 << bit) <= n + 1 && P[a][bit] == P[b][bit]) {
                a += (1 << bit);
                b += (1 << bit);
            }
        }
        rmq[i][0] = a - ord[i];
    }
    for(i = 2; i <= n; i++) {
        Log[i] = Log[i >> 1] + 1;
    }
    for(int bit = 1; bit < lg; bit++) {
        for(i = 1; i + (1 << bit) <= n; i++) {
            rmq[i][bit] = min(rmq[i][bit - 1], rmq[i + (1 << (bit - 1))][bit - 1]);
        }
    }
}

inline int get(int l, int r) {
    int bit = Log[r - l + 1];
    return min(rmq[l][bit], rmq[r - (1 << bit) + 1][bit]);
}

inline int solve(int pos, int len, int n) {
    int res1 = pos;
    for(int step = 1 << 18; step; step >>= 1) {
        if(res1 - step > 0 && get(res1 - step, pos - 1) >= len) {
            res1 -= step;
        }
    }
    int res2 = pos - 1;
    for(int step = 1 << 18; step; step >>= 1) {
        if(res2 + step < n && get(pos, res2 + step) >= len) {
            res2 += step;
        }
    }
    res2++;
    return res2 - res1 + 1;
}

ull pw[MAXN + 1], hsh[MAXN + 1];

inline ull get_hsh(int l, int r) {
    return hsh[r] - hsh[l - 1] * pw[r - l + 1];
}

int len[2 * MAXN + 5];

inline void manacher(int n) {
    vector <char> aux(2 * n + 5);
    int i, sz = 0;
    for(i = 1; i <= n; i++) {
        aux[++sz] = '*';
        aux[++sz] = str[i];
    }
    aux[++sz] = '*';
    int p = 0;
    for(i = 1; i <= sz; i++) {
        if(p + len[p] >= i) {
            len[i] = min(len[2 * p - i], p + len[p] - i);
        }
        while(i - len[i] > 0 && i + len[i] <= sz && aux[i - len[i]] == aux[i + len[i]]) {
            len[i]++;
        }
        if(i + len[i] > p + len[p]) {
            p = i;
        }
    }
}

map <ull, bool> mp;

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i;
    ios::sync_with_stdio(false);
    cin >> str + 1;
    int n = strlen(str + 1);
    suffix_array(n);
    manacher(n);
    pw[0] = 1;
    for(i = 1; i <= n; i++) {
        pw[i] = pw[i - 1] * B;
        hsh[i] = hsh[i - 1] * B + str[i] - 'a' + 1;
    }
    ll ans = 0;
    for(i = 2; i <= 2 * n; i++) {
        //cerr << i << " " << len[i] << "\n";
        if(i % 2 == 0) {
            for(int j = len[i] / 2; j >= 1; j--) {
                ull cur = get_hsh(i / 2 - j + 1, i / 2 + j - 1);
                if(mp[cur] == 0)  {
                    mp[cur] = 1;
                    ans = max(ans, 1LL * solve(where[i / 2 - j + 1], (2 * j - 1), n) * (2 * j - 1));
                }
                else {
                    break;
                }
            }
        }
        else {
            for(int j = len[i] / 2; j >= 1; j--) {
                ull cur = get_hsh(i / 2 - j + 1, i / 2 + j);
                if(mp[cur] == 0) {
                    //cerr << i / 2 - j + 1 << " " << i / 2 + j << "\n";
                    mp[cur] = 1;
                    ans = max(ans, 1LL * solve(where[i / 2 - j + 1], 2 * j, n) * 2 * j);
                }
                else {
                    break;
                }
            }
        }
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:151:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin >> str + 1;
            ~~~~^~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 552 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 2 ms 552 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Correct 2 ms 552 KB Output is correct
8 Correct 2 ms 552 KB Output is correct
9 Correct 2 ms 580 KB Output is correct
10 Correct 2 ms 580 KB Output is correct
11 Correct 2 ms 580 KB Output is correct
12 Correct 2 ms 664 KB Output is correct
13 Correct 2 ms 664 KB Output is correct
14 Correct 2 ms 704 KB Output is correct
15 Correct 2 ms 800 KB Output is correct
16 Correct 2 ms 800 KB Output is correct
17 Correct 2 ms 800 KB Output is correct
18 Correct 2 ms 800 KB Output is correct
19 Correct 2 ms 800 KB Output is correct
20 Correct 2 ms 800 KB Output is correct
21 Correct 2 ms 800 KB Output is correct
22 Correct 2 ms 800 KB Output is correct
23 Correct 2 ms 800 KB Output is correct
24 Correct 2 ms 800 KB Output is correct
25 Correct 2 ms 800 KB Output is correct
26 Correct 2 ms 800 KB Output is correct
27 Correct 2 ms 800 KB Output is correct
28 Correct 2 ms 804 KB Output is correct
29 Correct 2 ms 808 KB Output is correct
30 Correct 2 ms 812 KB Output is correct
31 Correct 2 ms 816 KB Output is correct
32 Correct 2 ms 820 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1080 KB Output is correct
2 Correct 3 ms 1084 KB Output is correct
3 Correct 3 ms 1084 KB Output is correct
4 Correct 4 ms 1084 KB Output is correct
5 Correct 3 ms 1084 KB Output is correct
6 Correct 3 ms 1084 KB Output is correct
7 Correct 3 ms 1084 KB Output is correct
8 Correct 3 ms 1084 KB Output is correct
9 Correct 3 ms 1084 KB Output is correct
10 Correct 3 ms 1084 KB Output is correct
11 Correct 3 ms 1084 KB Output is correct
12 Correct 3 ms 1084 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 3520 KB Output is correct
2 Correct 20 ms 3520 KB Output is correct
3 Correct 19 ms 3520 KB Output is correct
4 Correct 22 ms 3532 KB Output is correct
5 Correct 27 ms 3560 KB Output is correct
6 Correct 25 ms 3588 KB Output is correct
7 Correct 20 ms 3604 KB Output is correct
8 Correct 20 ms 3604 KB Output is correct
9 Correct 22 ms 3604 KB Output is correct
10 Correct 23 ms 3604 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 265 ms 27456 KB Output is correct
2 Correct 277 ms 27480 KB Output is correct
3 Correct 259 ms 27508 KB Output is correct
4 Correct 307 ms 27536 KB Output is correct
5 Correct 453 ms 27604 KB Output is correct
6 Correct 354 ms 27604 KB Output is correct
7 Correct 294 ms 27604 KB Output is correct
8 Correct 273 ms 27604 KB Output is correct
9 Correct 256 ms 27604 KB Output is correct
10 Correct 276 ms 27604 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1073 ms 80756 KB Time limit exceeded
2 Halted 0 ms 0 KB -