oj.uz

답안 #46690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
46690 2018-04-22T15:02:30 Z minkank 회문 (APIO14_palindrome) C++17
73 / 100
 1000 ms 62340 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = (ll) 1e9+9;
const ll base = 29;
int lg2[300005];
void prepLg2(int bound){
    for(int i=2;i<=bound;i++)
        lg2[i] = lg2[i>>1] + 1;
}
struct suffixArray{
    vector <int> sa, saRank, tmp;
    vector <vector <int> > lcp;
    int strLen, gap;

    bool saCmp(int x,int y){
        if (saRank[x] != saRank[y])
            return saRank[x] < saRank[y];
        return x+gap < strLen && y+gap < strLen ? saRank[x+gap] < saRank[y+gap] : x > y;
    }

    void build_lcp(string &s){
        int k = 0;
        for(int i = 0; i < strLen; i ++){
            if (saRank[i] != strLen - 1){
                for (int j = sa[saRank[i] + 1]; max(i+k, j+k) < strLen && s[i + k] == s[j + k];)  ++k;
                lcp[saRank[i]][0] = k;
                if (k) k--;
            }
        }
        for(int k = 1; k < 20; k ++){
            for(int i = 0; i < strLen; i ++)
                if (i + (1<<k) < strLen)
                    lcp[i][k] = min(lcp[i][k-1], lcp[i+(1<<(k-1))][k-1]);
                else break;
        }
    }

    int getLcp(int l,int r){
        if (l > r)  swap(l, r);
        if (l == r) return strLen - sa[l];
        int k = lg2[r - l];
        return min(lcp[l][k], lcp[r-(1<<k)][k]);
    }

    void build(string &s, int isIndexFromOne = 0){
        strLen = s.size();
        sa.assign(strLen + 5, 0);
        saRank.assign(strLen + 5, 0);
        tmp.assign(strLen + 5, 0);
        lcp.assign(strLen + 5, vector<int>(20));
        //for(int i = 0; i < strLen; i ++)
        //    lcp[i].assign(20, 0);

        for(int i = 0; i < strLen; i ++)
            sa[i] = i, saRank[i] = s[i];

        for(gap = 1;;gap *= 2){
            sort(sa.begin(), sa.begin() + strLen, [&](int a, int b) {return this->saCmp(a, b);});
            //sort(sa.begin(), sa.begin() + strLen, saCmp);
            for(int i = 0; i < strLen; i ++) tmp[i+1] = tmp[i] + saCmp(sa[i], sa[i+1]);
            for(int i = 0; i < strLen; i ++) saRank[sa[i]] = tmp[i];
            if (tmp[strLen-1] == strLen-1) break;
        }
        build_lcp(s);
    }
};
int n;
string s[2];
suffixArray suff;
ll hashCode[2][300000], pBase[300000];
void prepHash(){
    pBase[0] = 1;
    for(int i=1;i<300000;i++)
        pBase[i] = pBase[i-1] * base % mod;

    hashCode[0][0] = s[0][0] - 'a' + 1;
    hashCode[1][0] = s[1][0] - 'a' + 1;
    for(int i=1;i<n;i++)
        hashCode[0][i] = (hashCode[0][i-1] + pBase[i] * (s[0][i] - 'a' + 1)) % mod,
        hashCode[1][i] = (hashCode[1][i-1] + pBase[i] * (s[1][i] - 'a' + 1)) % mod;
}
bool checkPalindrome(int l1,int r1){
    int l2 = n-1-r1;
    int r2 = n-1-l1;
    ll val1 = (hashCode[0][r1] - (l1 == 0 ? 0 : hashCode[0][l1-1]) + mod) % mod;
    ll val2 = (hashCode[1][r2] - (l2 == 0 ? 0 : hashCode[1][l2-1]) + mod) % mod;
    val1 = val1 * pBase[max(0, r2 - r1)] % mod;
    val2 = val2 * pBase[max(0, r1 - r2)] % mod;
    return val1 == val2;
}

int get_hash(int l1, int r1) {
    ll val1 = hashCode[0][r1];
    if(l1) val1 -= 1LL * hashCode[0][l1 - 1] * pBase[r1 - l1 + 1];
    val1 = (val1 % mod + mod) % mod;
    return val1;
}

long long ans;
map<int, int> check;

long long solve(int p, int sz) {
    int id = suff.saRank[p];
    int l = id;
    for(int i = 18; i >= 0; --i) {
        int cur = l - (1 << i);
        if(cur < 0) continue;
        if(suff.lcp[cur][i] < sz) {
            if(1LL * sz * (n - cur) <= ans) return 0;
        }
        else l = cur;
    }
    int r = id;
    for(int i = 18; i >= 0; --i) {
        if(suff.lcp[r][i] < sz) {
            int cur = min(n - 1, r + (1 << i));
            if(1LL * sz * (cur - l + 1) <= ans) return 0;
        }
        else r = min(n - 1, r + (1 << i));
    }
    return 1LL * sz * (r - l + 1);
}

int main(){
    prepLg2(300000);
    iostream::sync_with_stdio(0);
    cin >> s[0];
    n = s[0].size();
    s[1] = s[0];
    reverse(s[1].begin(), s[1].end());
    suff.build(s[0]);
    prepHash();
    int sz0, sz1;
    sz0 = 0, sz1 = 1;
    ans = 0;
    for(int i = n - 1; i >= 0; --i) {
        int p0 = i + 2 * sz0 - 1; 
        int p1 = i + 2 * sz1 - 2;
        if(p0 >= i) {
            if(!check[get_hash(i, p0)]) {
                check[get_hash(i, p0)] = true;
                ans = max(ans, solve(i, p0 - i + 1));
            }
        }
        if(p1 >= i) {
            if(!check[get_hash(i, p1)]) {
                check[get_hash(i, p1)] = true;
                ans = max(ans, solve(i, p1 - i + 1));
            }
        }
        if(i == 0) continue;
        sz0++, sz1++;
        while(sz0) {
            p0 = i - 1 + 2 * sz0 - 1;
            if(!checkPalindrome(i - 1, p0)) sz0--;
            else break;
        }
        while(sz1) {
            p1 = i - 1 + 2 * sz1 - 2;
            if(!checkPalindrome(i - 1, p1)) sz1--;
            else break;
        }
    }
    cout << ans;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3832 KB Output is correct
2 Correct 6 ms 3944 KB Output is correct
3 Correct 6 ms 3944 KB Output is correct
4 Correct 7 ms 3944 KB Output is correct
5 Correct 6 ms 3960 KB Output is correct
6 Correct 6 ms 4088 KB Output is correct
7 Correct 6 ms 4136 KB Output is correct
8 Correct 8 ms 4136 KB Output is correct
9 Correct 8 ms 4140 KB Output is correct
10 Correct 6 ms 4140 KB Output is correct
11 Correct 7 ms 4140 KB Output is correct
12 Correct 7 ms 4140 KB Output is correct
13 Correct 7 ms 4140 KB Output is correct
14 Correct 7 ms 4140 KB Output is correct
15 Correct 7 ms 4140 KB Output is correct
16 Correct 6 ms 4140 KB Output is correct
17 Correct 6 ms 4140 KB Output is correct
18 Correct 7 ms 4140 KB Output is correct
19 Correct 6 ms 4140 KB Output is correct
20 Correct 7 ms 4140 KB Output is correct
21 Correct 8 ms 4140 KB Output is correct
22 Correct 6 ms 4140 KB Output is correct
23 Correct 7 ms 4148 KB Output is correct
24 Correct 7 ms 4148 KB Output is correct
25 Correct 7 ms 4148 KB Output is correct
26 Correct 6 ms 4148 KB Output is correct
27 Correct 6 ms 4148 KB Output is correct
28 Correct 6 ms 4148 KB Output is correct
29 Correct 6 ms 4148 KB Output is correct
30 Correct 7 ms 4148 KB Output is correct
31 Correct 6 ms 4148 KB Output is correct
32 Correct 7 ms 4148 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 6012 KB Output is correct
2 Correct 20 ms 6012 KB Output is correct
3 Correct 24 ms 6012 KB Output is correct
4 Correct 23 ms 6012 KB Output is correct
5 Correct 22 ms 6012 KB Output is correct
6 Correct 25 ms 6012 KB Output is correct
7 Correct 24 ms 6012 KB Output is correct
8 Correct 26 ms 6012 KB Output is correct
9 Correct 19 ms 6140 KB Output is correct
10 Correct 32 ms 6404 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 23528 KB Output is correct
2 Correct 267 ms 23548 KB Output is correct
3 Correct 268 ms 23548 KB Output is correct
4 Correct 269 ms 23548 KB Output is correct
5 Correct 343 ms 23676 KB Output is correct
6 Correct 288 ms 23676 KB Output is correct
7 Correct 245 ms 23676 KB Output is correct
8 Correct 264 ms 23776 KB Output is correct
9 Correct 266 ms 23776 KB Output is correct
10 Correct 472 ms 26984 KB Output is correct

Subtask #5
0 / 27.0

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