oj.uz

Submission #161593

# Submission time Handle Problem Language Result Execution time Memory
161593 2019-11-03T08:29:57 Z Akashi Palindromic Partitions (CEOI17_palindromic) C++14
0 / 100
 56 ms 23800 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;

    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:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &t);
     ~~~~~^~~~~~~~~~
palindromic.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", s + 1);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -