oj.uz

Submission #504013

# Submission time Handle Problem Language Result Execution time Memory
504013 2022-01-09T13:17:17 Z hieupy2k5 Necklace (Subtask 4) (BOI19_necklace4) C++14
15 / 15
 247 ms 516 KB 
#include<bits/stdc++.h>

using namespace std;

string s , t;
int p1[12345] , p2[12345];

struct Data
{
    int l , pos_s , pos_t;
};

Data Max(Data a , Data b)
{
    return (a.l > b.l) ? a : b;
}

Data get(string s , string t , bool ok)
{
    int n = s.size() , m = t.size();
    Data res = {0 , 0 , 0};

    for(int i = 0 ; i < n ; i++)
    {
        string s1 = s.substr(0 , i) , s2 = s.substr(i , n - 1) , t1 = t , t2 = t;
        reverse(s1.begin() , s1.end());
        reverse(t2.begin() , t2.end());

        s1 += '.' + t1;
        s2 += '.' + t2;

        for(int j = 1 ; j < s1.size() ; j++)
        {
            int k = p1[j - 1];
            while(k && s1[j] != s1[k]) k = p1[k - 1];
            if(s1[j] == s1[k]) k++;
            p1[j] = k;
        }

        for(int j = 1 ; j < s2.size() ; j++)
        {
            int k = p2[j - 1];
            while(k && s2[j] != s2[k]) k = p2[ - 1];
            if(s2[j] == s2[k]) k++;
            p2[j] = k;
        }

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

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    #define name "necklace"
    if(fopen(name".inp" , "r"))
    {
        freopen(name".inp" , "r" , stdin);
        freopen(name".out" , "w" , stdout);
    }

    cin>>s>>t;

    Data res = get(s , t , 0);
    reverse(t.begin() , t.end());
    res = Max(res , get(s , t , 1));

    cout<<res.l<<'\n';
    cout<<res.pos_s<<' '<<res.pos_t;
    return 0;
}

Compilation message

necklace.cpp: In function 'Data get(std::string, std::string, bool)':
necklace.cpp:32:27: 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 j = 1 ; j < s1.size() ; j++)
      |                         ~~^~~~~~~~~~~
necklace.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int j = 1 ; j < s2.size() ; j++)
      |                         ~~^~~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(name".inp" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         freopen(name".out" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp: In function 'Data get(std::string, std::string, bool)':
necklace.cpp:43:51: warning: array subscript -1 is below array bounds of 'int [12345]' [-Warray-bounds]
   43 |             while(k && s2[j] != s2[k]) k = p2[ - 1];
      |                                            ~~~~~~~^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 404 KB Output is correct
2 Correct 204 ms 452 KB Output is correct
3 Correct 247 ms 408 KB Output is correct
4 Correct 205 ms 392 KB Output is correct
5 Correct 132 ms 452 KB Output is correct
6 Correct 140 ms 320 KB Output is correct
7 Correct 173 ms 424 KB Output is correct
8 Correct 193 ms 416 KB Output is correct
9 Correct 204 ms 516 KB Output is correct