oj.uz

Submission #161596

# Submission time Handle Problem Language Result Execution time Memory
161596 2019-11-03T08:32:41 Z Akashi Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 2246 ms 25544 KB 
#include <bits/stdc++.h>
using namespace std;

const int H1 = 1e9 + 7;
const int H2 = 1e9 + 9;
const int N = 1e6 + 5;
const int P = 30;

int P1[N], P2[N];

struct weed{
    int h1, h2;

    weed(){h1 = 0; h2 = 0;}

    bool operator == (const weed &aux)const{
        if(h1 == aux.h1 && h2 == aux.h2) return 1;
        return 0;
    }

    void add(char c){
        h1 = (1LL * h1 * P + c - 'a' + 1) % H1;
        h2 = (1LL * h2 * P + c - 'a' + 1) % H2;
    }
    void add_rev(char c, int L){
        int x = c - 'a' + 1;
        h1 = (h1 + 1LL * x * P1[L]) % H1;
        h2 = (h2 + 1LL * x * P2[L]) % H2;
    }
};

weed suff[N], pref[N];

char s[N];

inline int lgput(int x, int p, int MOD){
    int aux = x, ans = 1;
    for(int i = 1; i <= p ; i = i << 1){
        if(i & p) ans = (1LL * aux * ans) % MOD;
        aux = (1LL * aux * aux) % MOD;

    }
    return ans;
}

weed find_suff(int l, int r, int out){
    weed aux;
    aux = suff[l];

    aux.h1 -= suff[r + 1].h1;
    aux.h2 -= suff[r + 1].h2;

    if(aux.h1 < 0) aux.h1 += H1;
    if(aux.h2 < 0) aux.h2 += H2;

    aux.h1 = (1LL * aux.h1 * lgput(P1[out], H1 - 2, H1)) % H1;
    aux.h2 = (1LL * aux.h2 * lgput(P2[out], H2 - 2, H2)) % H2;

    return aux;
}

weed find_pref(int l, int r){
    weed aux;
    int L = r - l + 1;
    aux = pref[r];

    aux.h1 = (aux.h1 - 1LL * pref[l - 1].h1 * P1[L]) % H1;
    aux.h2 = (aux.h2 - 1LL * pref[l - 1].h2 * P2[L]) % H2;

    if(aux.h1 < 0) aux.h1 += H1;
    if(aux.h2 < 0) aux.h2 += H2;

    return aux;
}

int main()
{
//    freopen("1.in", "r", stdin);

    int t, L;

    P1[0] = P2[0] = 1;
    for(int i = 1; i <= 1000000 ; ++i){
        P1[i] = (1LL * P1[i - 1] * P) % H1;
        P2[i] = (1LL * P2[i - 1] * P) % H2;
    }

    scanf("%d", &t);
    while(t--){
        scanf("%s", s + 1);
        L = strlen(s + 1);

        pref[0].h1 = pref[0].h2 = 0;
        for(int i = 1; i <= L ; ++i){
            pref[i] = pref[i - 1];
            pref[i].add(s[i]);
        }

        suff[L + 1].h1 = suff[L + 1].h2 = 0;;
        for(int i = L; i >= 1 ; --i){
            suff[i] = suff[i + 1];
            suff[i].add_rev(s[i], L - i);
        }

        int out = 0, l = 1, r = L, Sol = 0;
        weed aux1, aux2;
        for(int i1 = 1, i2 = L; i1 < i2 ; ++i1, --i2){
            aux1 = find_pref(l, i1);
            aux2 = find_suff(i2, r, out);

            if(aux1 == aux2){
                out += (i1 - l + 1);
                l = i1 + 1; r = i2 - 1;
                Sol = Sol + 2;
            }
        }

        if(l <= r) Sol = Sol + 1;

        printf("%d\n", Sol);
    }

    return 0;
}

Compilation message

palindromic.cpp: In function 'int main()':
palindromic.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &t);
     ~~~~~^~~~~~~~~~
palindromic.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", s + 1);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23800 KB Output is correct
2 Correct 29 ms 23800 KB Output is correct
3 Correct 29 ms 23800 KB Output is correct
4 Correct 30 ms 23800 KB Output is correct
5 Correct 29 ms 23800 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23800 KB Output is correct
2 Correct 29 ms 23800 KB Output is correct
3 Correct 29 ms 23800 KB Output is correct
4 Correct 30 ms 23800 KB Output is correct
5 Correct 29 ms 23800 KB Output is correct
6 Correct 30 ms 23800 KB Output is correct
7 Correct 30 ms 23800 KB Output is correct
8 Correct 31 ms 24056 KB Output is correct
9 Correct 31 ms 23800 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23800 KB Output is correct
2 Correct 29 ms 23800 KB Output is correct
3 Correct 29 ms 23800 KB Output is correct
4 Correct 30 ms 23800 KB Output is correct
5 Correct 29 ms 23800 KB Output is correct
6 Correct 30 ms 23800 KB Output is correct
7 Correct 30 ms 23800 KB Output is correct
8 Correct 31 ms 24056 KB Output is correct
9 Correct 31 ms 23800 KB Output is correct
10 Correct 51 ms 23916 KB Output is correct
11 Correct 42 ms 23904 KB Output is correct
12 Correct 50 ms 23928 KB Output is correct
13 Correct 47 ms 23928 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23800 KB Output is correct
2 Correct 29 ms 23800 KB Output is correct
3 Correct 29 ms 23800 KB Output is correct
4 Correct 30 ms 23800 KB Output is correct
5 Correct 29 ms 23800 KB Output is correct
6 Correct 30 ms 23800 KB Output is correct
7 Correct 30 ms 23800 KB Output is correct
8 Correct 31 ms 24056 KB Output is correct
9 Correct 31 ms 23800 KB Output is correct
10 Correct 51 ms 23916 KB Output is correct
11 Correct 42 ms 23904 KB Output is correct
12 Correct 50 ms 23928 KB Output is correct
13 Correct 47 ms 23928 KB Output is correct
14 Correct 2246 ms 25544 KB Output is correct
15 Correct 1171 ms 25336 KB Output is correct
16 Correct 2079 ms 25276 KB Output is correct
17 Correct 1203 ms 24696 KB Output is correct