oj.uz

Submission #773115

# Submission time Handle Problem Language Result Execution time Memory
773115 2023-07-04T15:24:41 Z hungby04 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 177 ms 604 KB 
/// HuDzG
#include <bits/stdc++.h>
#define reset(a) memset(a,0,sizeof(a))
#define ll long long
#define ld long double
#define endl '\n'
#define AutoAC int main()
#define OO 9000000000000000000
#define F first
#define S second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pb push_back
#define mp make_pair
#define nmax 1000005
#define HUNGIT ""
#define MOD 1000000007

using namespace std;

string s, t;
int res = 0;
pii pos;

vector <int> kmp(string t, string s, bool ok)
{
    t += ' ';
    vector <int> pi(t.length(), 0), res(s.length(), 0);
    for(int i = 1, j = 0; i < t.length(); i++)
    {
        while(j > 0 && t[i] != t[j]) j = pi[j - 1];
        if(t[i] == t[j]) j++;
        pi[i] = j;
    }
    for(int i = 0, j = 0; i < s.length(); i++)
    {
        while(j > 0 && s[i] != t[j]) j = pi[j - 1];
        if(s[i] == t[j]) j++;
        res[i] = j;
    }
    if(!ok) reverse(res.begin(), res.end());
    res.pb(0);
    return res;
}

void calc(string s, string t, bool ok)
{
    // cout << t << endl;
    string tmp = t;
    reverse(tmp.begin(), tmp.end());
    for(int i = 0; i <= s.length(); i++)
    {
        string x = s.substr(0, i), y = s.substr(i, (int)s.length() - i);
        reverse(x.begin(), x.end());
        vector <int> l = kmp(y, t, 1), r = kmp(x, tmp, 0);
        // cout << i << " " << r[0] << endl;
        if(r[0] > res)
        {
            res = r[0];
            pos = mp(i - r[0], ok ? 0 : (t.length() - 1) - r[0]);
            // cout << i << " " << r[0] << endl;
        }
        for(int j = 0; j < t.length(); j++)
            if(l[j] + r[j + 1] > res)
            {
                res = l[j] + r[j + 1];
                pos = mp(i - r[j + 1], ok ? j - l[j] + 1 : (t.length() - 1) - (j + r[j + 1]));
                // cout << y << " " << res << " " << i << " " << j << " " << l[j] << endl;
            }
    }
}

void solve()
{
    cin >> s >> t;
    calc(s, t, 1);
    reverse(t.begin(), t.end());
    calc(s, t, 0);
    cout << res << " " << pos.F << " " << pos.S;
}

AutoAC
{
    // clock_t START, FINISH;
    // START = clock();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen (HUNGIT".inp", "r", stdin);
    // freopen (HUNGIT".out", "w", stdout);
    int T = 1;

    // cin >> T;

    for (int i = 1; i <= T; i++)
    {
        solve();
    }

    // FINISH = clock();
    // cout << fixed << setprecision(4);
    // cout << endl << "TIME: " << (ld)((ld)(FINISH - START) / CLOCKS_PER_SEC);
    return 0;
}

Compilation message

necklace.cpp: In function 'std::vector<int> kmp(std::string, std::string, bool)':
necklace.cpp:29:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 1, j = 0; i < t.length(); i++)
      |                           ~~^~~~~~~~~~~~
necklace.cpp:35:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 0, j = 0; i < s.length(); i++)
      |                           ~~^~~~~~~~~~~~
necklace.cpp: In function 'void calc(std::string, std::string, bool)':
necklace.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0; i <= s.length(); i++)
      |                    ~~^~~~~~~~~~~~~
necklace.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j = 0; j < t.length(); j++)
      |                        ~~^~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 4 ms 372 KB Output is correct
7 Correct 3 ms 316 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 368 KB Output is correct
12 Correct 3 ms 340 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 4 ms 372 KB Output is correct
7 Correct 3 ms 316 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 368 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 165 ms 484 KB Output is correct
14 Correct 137 ms 476 KB Output is correct
15 Correct 177 ms 472 KB Output is correct
16 Correct 133 ms 472 KB Output is correct
17 Correct 114 ms 476 KB Output is correct
18 Correct 147 ms 604 KB Output is correct
19 Correct 136 ms 464 KB Output is correct
20 Correct 146 ms 480 KB Output is correct
21 Correct 152 ms 468 KB Output is correct