vingancadoleonardo.cpp

#include <bits/stdc++.h>
///Solucao em O(N log N)
#include <stdio.h>
#define MAX 105000
std::string s;
int N;
using ll = long long;
const ll MOD = 100000009LL;
const ll P = 7;
typedef std::pair<int,int> matriz;
ll pot[MAX];
matriz mult(matriz a,matriz b){
    matriz c = matriz(((((ll)a.first*(ll)pot[b.second])%MOD)+(ll)b.first)%MOD,a.second+b.second);
    return c;
}
///Armazena dados do hash
std::string casos[20][2];
matriz hash1[20],hash2[20];
matriz precalc[MAX][20];
int valido(int l,int r,int bit){///CHECA SE A SUBSTRING EH VALIDA COM HASH
    if(r>=N)return 0;
    if(hash1[bit]==precalc[l][bit]){
        for(int j=l;j!=l+(1<<bit);++j){
            if(casos[bit][0][j-l]!=s[j])return false;
        }
        return 1;
    }
    if(hash2[bit]==precalc[l][bit]){
        for(int j=l;j!=l+(1<<bit);++j){
            if(casos[bit][1][j-l]!=s[j])return false;
        }
        return 1;
    }
}
int tab[MAX][20][2];
bool existe[MAX][20][2];
int dp(int pos,int nivel,int dir){
    if(pos==N){
        return 0;
    }
    if(existe[pos][nivel][dir])return tab[pos][nivel][dir];
    existe[pos][nivel][dir]=1;
    int ans=1e9;
    ///Se puder pular, pula!
    if(valido(pos,pos+(1<<nivel)-1,nivel)){
        ans=std::min(ans,1+dp(pos+(1<<nivel),nivel,dir));
    }
    ///Menor q o nivel atual OU igual -> CASO ELE QUEIRA DECRESCER
    if(nivel>0)
        ans=std::min(ans,dp(pos,nivel-1,1));
    ///Maior q o nivel atual OU igual -> CASO ELE ESTEJA CRESCENDO
    if(!dir){
        if(nivel<19)
            ans=std::min(ans,1+dp(pos,nivel+1,0));
    }
    return tab[pos][nivel][dir]=ans;
}
///Funcao para gerar hash
matriz gera_matriz(int u){
    matriz b={u-47,1};
    return b;
}
///Funcao para gerar hash
matriz gera(std::string u){
    matriz a = {0,0};
    for(auto&x:u){
        a=mult(a,gera_matriz(x));
    }
    return a;
}
///Funcao para simular operacao 3 -> util enquanto geramos o hash
std::string dobra(std::string x){
    std::string u;
    for(auto&z:x){
        if(z=='0')u+="01";
        else u+="10";
    }
    return u;
}
int main()
{
    ///Inicializa o programa calculando os hashes: qual o hash caso a substring seja aplicada x vezes? Qual o hash da substring de l...r?
    pot[0]=1;
    for(int i=1;i!=MAX;++i)pot[i]=(pot[i-1]*P)%MOD;
    ///Inicializa cheques
    {
        std::string p = "1";
        for(int i=0;i!=20;++i){
            casos[i][0]=p;
            hash1[i]=gera(p);
            p=dobra(p);
        }
        p="0";
        for(int i=0;i!=20;++i){
            casos[i][1]=p;
            hash2[i]=gera(p);
            p=dobra(p);
        }
    }
    std::cin>>s;///Le a string e salva o tamanho como N
    N=s.size();
    ///Gera o hash da substring
    for(int i=0;i!=N;++i){
        precalc[i][0]=gera_matriz(s[i]);
    }
    for(int j=1;j!=20;++j){
        for(int i=0;i!=N;++i){
            if(i+(1<<j)<=N)
                precalc[i][j]=mult(precalc[i][j-1],precalc[i+(1<<(j-1))][j-1]);
        }
    }
    ///Chama a DP e printa a resposta
    int custo = dp(0,0,0);
    std::cout<<custo<<"\n";
}