oj.uz

Submission #466891

# Submission time Handle Problem Language Result Execution time Memory
466891 2021-08-21T00:04:44 Z Ozy Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 348 KB 
#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;
}

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;

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

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

    str devolver;

    devolver.val = der+1+r1;
    devolver.a = pa;
    devolver.b = pb - r1;
    if (ind == 2) devolver.b = tam[ind]-(devolver.b + devolver.val);

    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();

    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;
}

Subtask #1
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 36 ms 332 KB Output is correct
7 Correct 40 ms 332 KB Output is correct
8 Correct 152 ms 332 KB Output is correct
9 Correct 100 ms 336 KB Output is correct
10 Correct 14 ms 348 KB Output is correct
11 Correct 15 ms 348 KB Output is correct
12 Correct 126 ms 348 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 36 ms 332 KB Output is correct
7 Correct 40 ms 332 KB Output is correct
8 Correct 152 ms 332 KB Output is correct
9 Correct 100 ms 336 KB Output is correct
10 Correct 14 ms 348 KB Output is correct
11 Correct 15 ms 348 KB Output is correct
12 Correct 126 ms 348 KB Output is correct
13 Execution timed out 1574 ms 332 KB Time limit exceeded
14 Halted 0 ms 0 KB -