oj.uz

Submission #466890

# Submission time Handle Problem Language Result Execution time Memory
466890 2021-08-20T23:43:25 Z Ozy Necklace (Subtask 1-3) (BOI19_necklace1) C++17
9 / 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 + MIN, 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
5.0 / 25.0

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

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Partially correct 2 ms 332 KB Output is partially correct
3 Partially correct 3 ms 332 KB Output is partially correct
4 Correct 2 ms 332 KB Output is correct
5 Partially correct 1 ms 332 KB Output is partially correct
6 Partially correct 131 ms 332 KB Output is partially correct
7 Partially correct 78 ms 332 KB Output is partially correct
8 Correct 165 ms 332 KB Output is correct
9 Partially correct 99 ms 332 KB Output is partially correct
10 Partially correct 13 ms 332 KB Output is partially correct
11 Partially correct 15 ms 348 KB Output is partially correct
12 Correct 139 ms 332 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 Partially correct 2 ms 332 KB Output is partially correct
3 Partially correct 3 ms 332 KB Output is partially correct
4 Correct 2 ms 332 KB Output is correct
5 Partially correct 1 ms 332 KB Output is partially correct
6 Partially correct 131 ms 332 KB Output is partially correct
7 Partially correct 78 ms 332 KB Output is partially correct
8 Correct 165 ms 332 KB Output is correct
9 Partially correct 99 ms 332 KB Output is partially correct
10 Partially correct 13 ms 332 KB Output is partially correct
11 Partially correct 15 ms 348 KB Output is partially correct
12 Correct 139 ms 332 KB Output is correct
13 Execution timed out 1584 ms 332 KB Time limit exceeded
14 Halted 0 ms 0 KB -