oj.uz

Submission #460417

# Submission time Handle Problem Language Result Execution time Memory
460417 2021-08-09T06:33:01 Z bonopo Necklace (Subtask 4) (BOI19_necklace4) C++14
15 / 15
 296 ms 664 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define rc (i<<1)|1
#define lc (i<<1)
#define el "\n"
#define f first
#define s second

typedef long long ll;
const int MM=2e5+5, MOD=1e9+7, LOG=19;
pair<int,pair<int,int>> ans;
string s, t;

vector<int> lps(string k) {
    int m=k.size(), i=1, len=0;
    vector<int> ret(m+1);
    while(i<m) {
        if(k[i]==k[len]) ret[i++]=++len;
        else if(len) len=ret[len-1];
        else ret[i++]=0; }
    return ret;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>s>>t;
    for(int r=0, N=s.size(), M=t.size(); r<2; ++r) {
        for(int i=0; i<N; ++i) {
            string lft=s.substr(0, i), rvt=t, rit=s.substr(i);

            reverse(rvt.begin(), rvt.end());
            reverse(lft.begin(), lft.end());
            vector<int> lp=lps(lft+"$"+rvt), rp=lps(rit+"$"+t);

            for(int j=0; j<=M; ++j) {
                int len=rp[N-i+j]+lp[i+M-j];
                ans=max(ans, {len, {i-lp[i+M-j], (r?M-(j-rp[N-i+j]+len-1)-1:j-rp[N-i+j])}});
            }
        }

        reverse(begin(t), end(t));
    }

    cout<<ans.f<<el<<ans.s.f<<" "<<ans.s.s<<el;
}

// MM

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 664 KB Output is correct
2 Correct 202 ms 428 KB Output is correct
3 Correct 296 ms 436 KB Output is correct
4 Correct 184 ms 428 KB Output is correct
5 Correct 191 ms 440 KB Output is correct
6 Correct 270 ms 408 KB Output is correct
7 Correct 206 ms 448 KB Output is correct
8 Correct 224 ms 440 KB Output is correct
9 Correct 237 ms 432 KB Output is correct