oj.uz

Submission #514511

# Submission time Handle Problem Language Result Execution time Memory
514511 2022-01-18T08:30:17 Z Mahdi Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 448 ms 452 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;
                break;
            }
            if(x==0)
                break;
            x=f[x-1];
        }
    }
}

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;
                break;
            }
            if(x==0)
                break;
            x=g[x-1];
        }
    }
}

pair<int, pii> kmp(bool bl){
    u=s+"#"+t;
    //cout<<u<<'\n';
    opr1();
    u=t+"#"+s;
    reverse(all(u));
    //cout<<u<<'\n';
    opr2();
    /*for(int i=0;i<u.size();++i)
        cout<<f[i]<<' ';
    cout<<'\n';
    for(int i=0;i<u.size();++i)
        cout<<g[i]<<' ';
    cout<<"\n\n";*/
    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((bl && x>=z.F) || x>z.F){
            z.F=x;
            z.S.F=g[n+m-1-i];
            z.S.S=i-f[1+n+i]+1;
        }
    }
    if((!bl && g[n+m]>=z.F) || g[n+m]>z.F){
        z.F=g[n+m];
        z.S.F=g[n+m];
        z.S.S=0;
    }
    if((bl && f[m+n]>=z.F) || 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(bool bl){
    pair<int, pii> res, c;
    res.F=0;
    for(int i=0;i<n;++i){
        //cout<<i<<" : \n";
        c=kmp(bl);
        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(0);
    reverse(all(t));
    c=sol(1);
    if(c.F>ans.F){
        c.S.S=m-c.S.S-c.F;
        ans=c;
    }
    cout<<ans.F<<'\n';
    cout<<ans.S.F<<' '<<ans.S.S<<'\n';
}

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:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=1;i<u.size();++i){
      |                 ~^~~~~~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 8 ms 316 KB Output is correct
7 Correct 7 ms 336 KB Output is correct
8 Correct 9 ms 204 KB Output is correct
9 Correct 7 ms 332 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 4 ms 332 KB Output is correct
12 Correct 6 ms 328 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 8 ms 316 KB Output is correct
7 Correct 7 ms 336 KB Output is correct
8 Correct 9 ms 204 KB Output is correct
9 Correct 7 ms 332 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 4 ms 332 KB Output is correct
12 Correct 6 ms 328 KB Output is correct
13 Correct 397 ms 384 KB Output is correct
14 Correct 336 ms 452 KB Output is correct
15 Correct 448 ms 384 KB Output is correct
16 Correct 388 ms 384 KB Output is correct
17 Correct 207 ms 376 KB Output is correct
18 Correct 211 ms 376 KB Output is correct
19 Correct 289 ms 332 KB Output is correct
20 Correct 364 ms 380 KB Output is correct
21 Correct 365 ms 384 KB Output is correct