oj.uz

Submission #444821

# Submission time Handle Problem Language Result Execution time Memory
444821 2021-07-15T13:44:16 Z prvocislo Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 665 ms 564 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

void pf_function(const string &s, vector<int> &p)
{
    p.resize(s.size());
    p[0] = 0;
    for (int i = 1; i < s.size(); i++)
    {
        int j = p[i-1];
        while (j && s[i] != s[j]) j = p[j-1];
        if (s[i] == s[j]) j++;
        p[i] = j;
    }
    /*cout << "\n" << s << "\n";
    for (int i = 0; i < p.size(); i++) cout << p[i] << " ";
    cout << endl;*/
}
vector<int> best(const string &s, const string &t, bool rv)
{
    int n = s.size(), m = t.size();
    vector<int> ans = {0, 0, 0};
    for (int i = 0; i < n; i++) // skusime kde rozrezat s
    {
        //cout << i << endl;
        string s1 = s.substr(0, i), s2 = s.substr(i, n-i);
        string t1 = t;
        reverse(t1.begin(), t1.end()), reverse(s1.begin(), s1.end());
        vector<int> v1, v2;
        pf_function(s1 + "#" + t1, v1);
        pf_function(s2 + "#" + t, v2);
        for (int j = 0; j < m; j++)
        {
            int a = v1[v1.size() - j - 1], b = v2[s2.size() + j];
            int si = i - a, ti = j - b;
            if (rv) ti = m - (ti+a+b-1) - 1;
            ans = max(ans, {a+b, si, ti});
        }
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s, t;
    cin >> s >> t;
    vector<int> ans = best(s, t, false);
    reverse(t.begin(), t.end());
    ans = max(ans, best(s, t, true));
    cout << ans[0] << "\n" << ans[1] << " " << ans[2] << "\n";
    return 0;
}

Compilation message

necklace.cpp: In function 'void pf_function(const string&, std::vector<int>&)':
necklace.cpp:9:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i = 1; i < s.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is 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 13 ms 332 KB Output is correct
7 Correct 13 ms 364 KB Output is correct
8 Correct 14 ms 356 KB Output is correct
9 Correct 12 ms 332 KB Output is correct
10 Correct 12 ms 332 KB Output is correct
11 Correct 11 ms 364 KB Output is correct
12 Correct 12 ms 360 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is 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 13 ms 332 KB Output is correct
7 Correct 13 ms 364 KB Output is correct
8 Correct 14 ms 356 KB Output is correct
9 Correct 12 ms 332 KB Output is correct
10 Correct 12 ms 332 KB Output is correct
11 Correct 11 ms 364 KB Output is correct
12 Correct 12 ms 360 KB Output is correct
13 Correct 659 ms 440 KB Output is correct
14 Correct 611 ms 496 KB Output is correct
15 Correct 665 ms 484 KB Output is correct
16 Correct 652 ms 432 KB Output is correct
17 Correct 544 ms 452 KB Output is correct
18 Correct 551 ms 332 KB Output is correct
19 Correct 607 ms 564 KB Output is correct
20 Correct 611 ms 520 KB Output is correct
21 Correct 632 ms 452 KB Output is correct