oj.uz

Submission #513763

# Submission time Handle Problem Language Result Execution time Memory
513763 2022-01-17T15:06:32 Z Mahdi Necklace (Subtask 1-3) (BOI19_necklace1) C++17
17 / 85
 354 ms 392 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==f[x])
                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;
                break;
            }
            if(x==g[x])
                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';
}
/*
xnvnnqfwnxcvzyakzhnpepdbadkjktyqktjasudbxaasmkfnphalwubd
zjnvfbfqalosvcdabdpepnhzjtkqytkjkcczu

vzyakzhnpepdbadkjktyqktjasudbxaasmkfnphalwubd
alosvcdabdpepnhzjtkqytkjkcczu

vzyakzhnpepdbadkjktyqktjasudb
alosvcdabdpepnhzjtkqytkjkcczu

zhnpepdbadkjktyqktj
dabdpepnhzjtkqytkjk
*/

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
5.0 / 25.0

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

Subtask #2
4.0 / 20.0

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

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 316 KB Output is partially correct
2 Partially correct 1 ms 204 KB Output is partially correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 6 ms 332 KB Output is correct
7 Correct 7 ms 332 KB Output is correct
8 Partially correct 6 ms 204 KB Output is partially correct
9 Correct 7 ms 204 KB Output is correct
10 Correct 5 ms 328 KB Output is correct
11 Correct 5 ms 332 KB Output is correct
12 Correct 5 ms 332 KB Output is correct
13 Partially correct 276 ms 380 KB Output is partially correct
14 Partially correct 319 ms 380 KB Output is partially correct
15 Partially correct 298 ms 388 KB Output is partially correct
16 Partially correct 354 ms 384 KB Output is partially correct
17 Correct 236 ms 380 KB Output is correct
18 Correct 244 ms 380 KB Output is correct
19 Correct 246 ms 332 KB Output is correct
20 Correct 255 ms 388 KB Output is correct
21 Correct 265 ms 392 KB Output is correct