oj.uz

Submission #290108

# Submission time Handle Problem Language Result Execution time Memory
290108 2020-09-03T12:12:07 Z alexandra_udristoiu Necklace (Subtask 4) (BOI19_necklace4) C++14
15 / 15
 631 ms 504 KB 
#include<iostream>
#include<cstring>
using namespace std;
int n, m, i, j, sol, x, ii, jj, val, nr;
int d[3005], ds[3005], z[6005];
char a[3005], b[3005], s[6005];
void zet(){
    int i, ii = 0;
    for(i = 2; i <= nr; i++){
        if(ii + z[ii] - 1 >= i){
            z[i] = min(ii + z[ii] - i, z[i - ii + 1]);
        }
        else{
            z[i] = 0;
        }
        while(i + z[i] <= nr && s[ z[i] + 1 ] == s[ i + z[i] ]){
            z[i]++;
        }
        if(i + z[i] > ii + z[ii]){
            ii = i;
        }
    }
}
void solve(int t){
    for(i = 1; i <= n; i++){
        nr = 0;
        for(j = i; j <= n; j++){
            s[++nr] = a[j];
        }
        s[++nr] = '*';
        for(j = 1; j <= m; j++){
            s[++nr] = b[j];
        }
        zet();
        x = m;
        for(j = nr; j >= nr - m + 1; j--){
            d[x] = z[j];
            x--;
        }
        nr = 0;
        for(j = i - 1; j >= 1; j--){
            s[++nr] = a[j];
        }
        s[++nr] = '*';
        for(j = m; j >= 1; j--){
            s[++nr] = b[j];
        }
        zet();
        memset(ds, 0, sizeof(ds) );
        x = m;
        for(j = i + 1; j <= nr; j++){
            ds[ x - z[j] + 1] = max(z[j], ds[ x - z[j] + 1 ]);
            x--;
        }
        for(j = 2; j <= m; j++){
            ds[j] = max(ds[j], ds[j - 1] - 1);
        }

        for(j = 1; j <= m; j++){
            val = d[j] + ds[ j + d[j] ];
            if(val > sol){
                sol = val;
                if(t == 0){
                    jj = j;
                }
                else{
                    jj = j + val - 1;
                    jj = m - jj + 1;
                }
                ii = i - ds[ j + d[j] ];
            }
            sol = max(sol, d[j] + ds[ j + d[j] ]);
        }
    }
}
int main(){
    cin>> a + 1;
    n = strlen(a + 1);
    cin>> b + 1;
    m = strlen(b + 1);
    solve(0);
    for(i = 1, j = m; i < j; i++, j--){
        swap(b[i], b[j]);
    }
    solve(1);
    cout<< sol <<"\n";
    cout<< ii - 1 <<" "<< jj - 1 <<"\n";
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:77:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |     cin>> a + 1;
      |           ~~^~~
necklace.cpp:79:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |     cin>> b + 1;
      |           ~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 424 KB Output is correct
2 Correct 578 ms 424 KB Output is correct
3 Correct 631 ms 384 KB Output is correct
4 Correct 562 ms 420 KB Output is correct
5 Correct 466 ms 428 KB Output is correct
6 Correct 457 ms 384 KB Output is correct
7 Correct 523 ms 384 KB Output is correct
8 Correct 519 ms 384 KB Output is correct
9 Correct 528 ms 504 KB Output is correct