제출 #1313057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313057		davidc	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	617 ms	2700 KiB

necklace

#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
using namespace std;

typedef unsigned short u16;

struct Respuesta{
    int largo = 0;
    int inicioS = 0;
    int inicioT = 0;
};

void invertir_string(string &x){
    reverse(all(x));
}

Respuesta resolver_orientacion(const string &S, const string &T){
    int n = (int)S.size();
    int m = (int)T.size();


    string Sr = S, Tr = T;
     reverse(all(Sr));
     reverse(all(Tr));


    const int BLOQUE = 380;

    Respuesta mejor;


    vector<u16> dp(m + 1, 0), ndp(m + 1, 0);
    vector<u16> dp2(m + 1, 0), ndp2(m + 1, 0);


    vector<u16> filaLSP(m + 1, 0);


    for(int a0 = 0; a0 <= n; a0 += BLOQUE){
        int a1 = min(n + 1, a0 + BLOQUE);
        int filas = a1 - a0;

        vector<u16> almacen((size_t)filas * (m + 1), 0);

        auto ptr_fila = [&](int idx)->u16*{
            return &almacen[(size_t)idx * (m + 1)];
        };


        fill(all(dp), 0);
        fill(all(ndp), 0);


        for(int a = 1; a <= n; a++){
            ndp[0] = 0;
            for(int b = 1; b <= m; b++){
                if(Sr[a - 1] == Tr[b - 1]) ndp[b] = (u16)(dp[b - 1] + 1);
                else ndp[b] = 0;
            }
            dp.swap(ndp);

            if(a0 <= a && a < a1){

                fill(all(filaLSP), 0);

                for(int b = 1; b <= m; b++){
                    u16 l = dp[b];
                    if(l){
                        int inicio = b - (int)l;
                        if(filaLSP[inicio] < l) filaLSP[inicio] = l;
                    }
                }

                for(int j = 1; j <= m; j++){
                    u16 dec = (filaLSP[j - 1] ? (u16)(filaLSP[j - 1] - 1) : 0);
                    if(filaLSP[j] < dec) filaLSP[j] = dec;
                }

                u16 *dest = ptr_fila(a - a0);
                memcpy(dest, filaLSP.data(), (m + 1) * sizeof(u16));
            }
        }


        int i_min = n - (a1 - 1);
        int i_max = n - a0;
        i_min = max(i_min, 0);
        i_max = min(i_max, n);

        fill(all(dp2), 0);
        fill(all(ndp2), 0);

        for(int i = 0; i <= n; i++){
            if(i == 0){
                fill(all(filaLSP), 0);
            }else{
                ndp2[0] = 0;
                for(int j = 1; j <= m; j++){
                    if(S[i - 1] == T[j - 1]) ndp2[j] = (u16)(dp2[j - 1] + 1);
                    else ndp2[j] = 0;
                }
                dp2.swap(ndp2);

                fill(all(filaLSP), 0);
                for(int j = 1; j <= m; j++){
                    u16 l = dp2[j];
                    if(l){
                        int inicio = j - (int)l;
                        if(filaLSP[inicio] < l) filaLSP[inicio] = l;
                    }
                }
                for(int j = 1; j <= m; j++){
                    u16 dec = (filaLSP[j - 1] ? (u16)(filaLSP[j - 1] - 1) : 0);
                    if(filaLSP[j] < dec) filaLSP[j] = dec;
                }
            }

            if(i < i_min || i > i_max) continue;

            int a = n - i;
            int idx = a - a0;
            u16 *filaRev = ptr_fila(idx);


            for(int j = 0; j <= m; j++){
                int la = (int)filaLSP[j];
                int lb = (int)filaRev[m - j];
                int L = la + lb;

                if(L > mejor.largo){
                    mejor.largo = L;
                    mejor.inicioS = i - la;
                    mejor.inicioT = j - lb;
                }
            }
        }
    }

    return mejor;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string S, T;
    cin >> S >> T;
    int m = (int)T.size();


    Respuesta r1 = resolver_orientacion(S, T);


    string Trev = T;
    reverse(all(Trev));
    Respuesta r2 = resolver_orientacion(S, Trev);


    int inicioT_mapeado = m - (r2.inicioT + r2.largo);


    Respuesta mejor = r1;
    int mejorInicioT = r1.inicioT;

    if(r2.largo > mejor.largo){
        mejor = r2;
        mejorInicioT = inicioT_mapeado;
    }

    cout << mejor.largo << "\n";
    cout << mejor.inicioS << " " << mejorInicioT << "\n";

    return 0;
}

• Subtask 1: 15 / 15