oj.uz

Submission #867208

# Submission time Handle Problem Language Result Execution time Memory
867208 2023-10-27T21:20:49 Z BBart888 Necklace (Subtask 4) (BOI19_necklace4) C++14
15 / 15
 314 ms 828 KB 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#include <stack>
#include <stdio.h>      
#include <stdlib.h>     
#include <time.h> 
#include <string>
#include <fstream>



using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;



using Mat = vector<vector<ll>>;
const ll MOD = 1e9 + 7;
const int MAXN = 7e3 + 111;



string a, b;

vector<int> pref_func(string s)
{
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++)
    {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}


tuple<int, int, int> solve(string s, string t, bool rev)
{
    int n = s.size();
    int m = t.size();
        
    tuple<int, int, int> ans = { 0,0,0 };
    for (int i = 0; i < n; i++)
    {
        string s1 = s.substr(0, i);
        string s2 = s.substr(i, n - i);
        reverse(s1.begin(), s1.end());
        string t1 = t;
        string t2 = t;
        reverse(t2.begin(), t2.end());
        vector<int> p1 = pref_func(s1 + "#" + t1);
        vector<int> p2 = pref_func(s2 + "#" + t2);

        for (int j = 1; j <= m; j++)
            ans = max(ans, {p1[i+j] + p2[n+m-i-j],i-p1[i+j], rev ? 
                m - j - p2[n+m-i-j] : 
                j - p1[i+j]});
    }
    return ans;
}





int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);



    //freopen("boards.in", "r", stdin);
    //freopen("boards.out", "w", stdout);
   

    cin >> a >> b;

    tuple<int, int, int> ans = solve(a, b, false);
    reverse(b.begin(), b.end());
    ans = max(ans, solve(a, b, true));

    cout << get<0>(ans) << '\n' << get<1>(ans) << ' ' << get<2>(ans) << ' ';


    







    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 576 KB Output is correct
2 Correct 251 ms 828 KB Output is correct
3 Correct 314 ms 344 KB Output is correct
4 Correct 238 ms 592 KB Output is correct
5 Correct 200 ms 580 KB Output is correct
6 Correct 221 ms 344 KB Output is correct
7 Correct 233 ms 592 KB Output is correct
8 Correct 257 ms 572 KB Output is correct
9 Correct 265 ms 348 KB Output is correct