oj.uz

Submission #1076641

# Submission time Handle Problem Language Result Execution time Memory
1076641 2024-08-26T15:12:55 Z vjudge1 Necklace (Subtask 4) (BOI19_necklace4) C++17
15 / 15
 212 ms 596 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task ""
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
#define all(s) s.begin(), s.end()
using namespace std;
const int nmax = 3002;
string s, t;
int n, m;
tii ans = {0, 0, 0};

vector <int> kmp(string s)
{
    vector <int> res(s.size());
    int k = 0;
    for(int i = 1; i < s.size(); ++i)
    {
        while(k && s[i] != s[k])
            k = res[k - 1];
        res[i] = (s[i] == s[k] ? ++k : 0);
    }
    return res;
}

int revpos(int p, int len)
{
    return len - p - 1;
}

void solve(bool rev)
{
    for (int i = 0; i < n; ++i)
    {
        string s1 = s.substr(0, i);
        string s2 = s.substr(i, n - i);
        reverse(all(s1));
        
        string t1 = t, t2 = t;
        reverse(all(t2));

        vector <int> p1 = kmp(s1 + '!' + t2), p2 = kmp(s2 + '!' + t1);
        for (int j = 0; j < m; ++j)
        {
            int x = p2[j + s2.size() + 1];
            int y = p1[revpos(j + 1, m) + s1.size() + 1];
            ans = max(ans, make_tuple(x + y, i - y, (!rev ? j - x + 1 : revpos(j + y, m))));
        }
    }
}

int main()
{
    if (ifstream(task".inp")) nx
    fast

    cin >> s >> t;
    n = s.size(), m = t.size();
    solve(0);
    reverse(all(t));
    solve(1);
    cout << get<0>(ans) << '\n' << get<1>(ans) << ' ' << get<2>(ans);
}

Compilation message

necklace.cpp: In function 'std::vector<int> kmp(std::string)':
necklace.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i = 1; i < s.size(); ++i)
      |                    ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:7:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:60:31: note: in expansion of macro 'nx'
   60 |     if (ifstream(task".inp")) nx
      |                               ^~
necklace.cpp:7:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:60:31: note: in expansion of macro 'nx'
   60 |     if (ifstream(task".inp")) nx
      |                               ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 344 KB Output is correct
2 Correct 159 ms 596 KB Output is correct
3 Correct 212 ms 348 KB Output is correct
4 Correct 146 ms 348 KB Output is correct
5 Correct 105 ms 576 KB Output is correct
6 Correct 108 ms 348 KB Output is correct
7 Correct 135 ms 348 KB Output is correct
8 Correct 165 ms 344 KB Output is correct
9 Correct 163 ms 572 KB Output is correct