oj.uz

Submission #513694

# Submission time Handle Problem Language Result Execution time Memory
513694 2022-01-17T12:21:33 Z Mahdi Necklace (Subtask 1-3) (BOI19_necklace1) C++17
0 / 85
 1500 ms 204 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=3e3+5;
int n, m, f[2*N], g[2*N];
string s, t, u;

void opr1(){
    int x;
    for(int i=1;i<u.size();++i){
        f[i]=0;
        x=f[i-1];
        while(true){
            if(u[i]==u[x])
                f[i]=x+1;
            if(x==0)
                break;
            x=f[x];
        }
    }
}

void opr2(){
    int x;
    for(int i=1;i<u.size();++i){
        g[i]=0;
        x=g[i-1];
        while(true){
            if(u[i]==u[x])
                g[i]=x+1;
            if(x==0)
                break;
            x=g[x];
        }
    }
}

pair<int, pii> kmp(){
    u=s+"#"+t;
    opr1();
    u=t+"#"+s;
    reverse(all(u));
    opr2();
    pair<int, pii> z;
    int x;
    for(int i=0;i<m-1;++i){
        x=f[1+n+i]+g[n+m-1-i];
        if(x>z.F){
            z.F=x;
            z.S.F=g[n+m-1-i];
            z.S.S=i-f[1+n+i]+1;
        }
    }
    if(g[n+m]>z.F){
        z.F=g[n+m];
        z.S.F=g[n+m];
        z.S.S=0;
    }
    if(f[m+n]>z.F){
        z.F=f[m+n];
        z.S.F=0;
        z.S.S=m-f[m+n];
    }
    return z;
}

pair<int, pii> sol(){
    pair<int, pii> res, c;
    res.F=0;
    for(int i=0;i<n;++i){
        c=kmp();
        if(c.F>res.F){
            c.S.F=i-c.S.F;
            res=c;
        }
        char z=s[0];
        for(int j=0;j<n-1;++j)
            s[j]=s[j+1];
        s[n-1]=z;
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>s>>t;
    s+="*";
    n=s.size();
    m=t.size();
    pair<int, pii>ans, c;
    ans=sol();
    reverse(all(t));
    c=sol();
    if(c.F>ans.F){
        c.S.S=m-c.S.S-c.F;
        ans=c;
    }
    cout<<ans.F<<'\n'<<ans.S.F<<' '<<ans.S.S<<'\n';
}
/*
abcdefghiyzrhonxsh
cdefzfghklrzynohxsh
*/

Compilation message

necklace.cpp: In function 'void opr1()':
necklace.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=1;i<u.size();++i){
      |                 ~^~~~~~~~~
necklace.cpp: In function 'void opr2()':
necklace.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=1;i<u.size();++i){
      |                 ~^~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1532 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1532 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1532 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -