Submission #466888

#	Time	Username	Problem	Language	Result	Execution time	Memory
466888		Ozy	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	9 / 85	1576 ms	352 KiB

necklace

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define mod 1000000007
#define prim 29
#define MAX 3000

struct str{
    lli val;
    lli a;
    lli b;
};

string st[3];
lli acu[3][MAX+2],tam[3], divi[MAX+4], pot[MAX+4];
lli n,m,k,sss;
str x,res;

void inverso() {

    lli res = 1;
    lli pot = prim;
    lli num = mod-2;
    while (num > 0) {
        if (num&1) {
            res *= pot;
            res %= mod;
        }
        num/=2;
        pot *= pot;
        pot %= mod;
    }

    divi[0] = 1;
    divi[1] = res;
    rep(i,2,max(tam[0],tam[1])) {divi[i] = divi[i-1]*res; divi[i]%=mod;}
}

lli query(lli ini, lli fin, lli ind) {

    lli res = acu[ind][fin];
    if (ini > 0) res -= acu[ind][ini-1];
    if (res < 0) res += mod;

    res *= divi[ini];
    res %= mod;

    return res;
}

lli Rbinaria(lli ini, lli fin, lli pa, lli pb, lli ind) {

    lli mitad,a,b,sa,sb,dist = 0;
    while (ini <= fin) {
        mitad = (ini+fin)/2;
        a = pa+mitad;
        b = pb+mitad;

        sa = query(pa,a,0);
        sb = query(pb,b,ind);

        if (sa == sb){
            dist = mitad;
            ini = mitad+1;
        }
        else fin = mitad-1;
    }

    return dist;
}

lli Ibinaria(lli ini, lli fin, lli pa, lli pb, lli ind) {

    lli mitad,a,b,sa,sb,dist = 0;
    while (ini <= fin) {
        mitad = (ini+fin)/2;
        a = pa-mitad;
        b = pb-mitad;

        sa = query(a,pa,0);
        sb = query(b,pb,ind);

        if (sa == sb){
            dist = mitad;
            ini = mitad+1;
        }
        else fin = mitad-1;
    }

    return dist;
}

str solve(lli pa, lli pb, lli ind) {

    lli MIN = min(tam[0]-pa-1, tam[ind]-pb-1);
    lli der = Rbinaria(1,MIN,pa,pb,ind);

    lli r1 = 0;
    lli r2 = 0;

    MIN = min(pb, tam[0] - (pa + der) - 1);
    repa(i, MIN, 1) {
        lli q = query(pa + der + 1, pa + der + MIN, 0);
        lli w = query(pb - i, pb - 1, ind);

        if (q == w) {
            r1 = i;
            break;
        }
    }


    MIN = min(pa, tam[ind] - (pb + der) - 1);
    repa(i, MIN, 1) {
        lli q = query(pb + der + 1, pb + der + MIN, ind);
        lli w = query(pa - i, pa - 1, 0);

        if (q == w) {
            r2 = i;
            break;
        }
    }

    str devolver;

    devolver.val = der+1+max(r1,r2);
    if (r1 > r2){
        devolver.a = pa;
        devolver.b = pb - r1;
        if (ind == 2) devolver.b = tam[ind]-(devolver.b + devolver.val);
    }
    else {
        devolver.a = pa - r2;
        devolver.b = pb;
        if (ind == 2) devolver.b = tam[ind]-(devolver.b + devolver.val);
    }
    //debugsl(devolver.val);
    //debugsl(devolver.a);
    //debug(devolver.b);

    return devolver;
}


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

    cin >> st[0] >> st[1];
    st[2] = st[1];
    reverse(st[2].begin(), st[2].end());

    tam[0] = st[0].size();
    tam[1] = tam[2] = st[1].size();

    rep(z,0,2) {
        pot[0] = 1;
        rep(i,0,tam[z]-1){

            k = st[z][i] - 'a';
            k++;
            k *= pot[i];
            acu[z][i] = k;
            if (i > 0) acu[z][i] += acu[z][i-1];
            acu[z][i] %= mod;

            pot[i+1] = pot[i]*prim;
            pot[i+1] %= mod;
        }
    }
    inverso();

    lli a,b,c,d,ind;
    //while (a != -1) {
    //    cin >> a >> b >> c >> d >> ind;
    //    if (a == -1) break;
    //    cout << query(a,b,0) << endl;
    //    cout << query(c,d,ind) << endl;
    //}


    rep(pp,0,tam[0]-1) {
        rep(ss,0,tam[1]-1){

            if (st[0][pp] == st[1][ss]) {

                x = solve(pp,ss,1);
                if (x.val > res.val) res = x;

                sss = tam[1]-ss-1;
                x = solve(pp,sss,2);
                if (x.val > res.val) res = x;


            }

        }
    }

    cout << res.val << "\n";
    cout << res.a << ' ' << res.b;
}

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:180:9: warning: unused variable 'a' [-Wunused-variable]
  180 |     lli a,b,c,d,ind;
      |         ^
necklace.cpp:180:11: warning: unused variable 'b' [-Wunused-variable]
  180 |     lli a,b,c,d,ind;
      |           ^
necklace.cpp:180:13: warning: unused variable 'c' [-Wunused-variable]
  180 |     lli a,b,c,d,ind;
      |             ^
necklace.cpp:180:15: warning: unused variable 'd' [-Wunused-variable]
  180 |     lli a,b,c,d,ind;
      |               ^
necklace.cpp:180:17: warning: unused variable 'ind' [-Wunused-variable]
  180 |     lli a,b,c,d,ind;
      |                 ^~~

• Subtask 1: 5 / 25
• Subtask 2: 4 / 20
• Subtask 3: 0 / 40