oj.uz

Submission #140736

# Submission time Handle Problem Language Result Execution time Memory
140736 2019-08-04T19:20:05 Z Minnakhmetov Necklace (Subtask 1-3) (BOI19_necklace1) C++14
85 / 85
 354 ms 504 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 6005;
string a, b;
int p1[N], p2[N];

void prefixFunction(string a, const string &b, int p[N]) {
    a = a + "#" + b;

    p[0] = 0;

    for (int i = 1; i < a.size(); i++) {
        int x = p[i - 1];
        while (x > 0 && a[x] != a[i])
            x = p[x - 1];
        if (a[x] == a[i])
            x++;
        p[i] = x;
    }

    for (int i = 0; i < b.size(); i++)
        p[i] = p[a.size() - b.size() + i];
}

tuple<int, int, int> calc(string a, string b, bool rev) {
    b += '$';

    int ans = -1, x, y;

    for (int i = 0; i < b.size() - 1; i++) {
        prefixFunction(b, a, p1);
        reverse(all(b));
        reverse(all(a));
        prefixFunction(b, a, p2);
        reverse(p2, p2 + a.size());
        reverse(all(b));
        reverse(all(a));        

        for (int j = -1; j < (int)a.size(); j++) {
            int cur = 0;

            if (j >= 0)
                cur += p1[j];
            if (j + 1 < a.size())
                cur += p2[j + 1];

            if (cur > ans) {
                ans = cur;
                x = (j < 0 ? 0 : j - p1[j] + 1);
                y = i - (j + 1 < a.size() ? p2[j + 1] : 0);
            }
        }

        for (int j = 0; j < b.size() - 1; j++)
            swap(b[j], b[j + 1]);
    }

    if (rev)
        y = b.size() - 1 - y - ans;

    return { ans, x, y };
}

signed main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> a >> b;

    auto ans = calc(a, b, false);
    reverse(all(b));
    ans = max(ans, calc(a, b, true));

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

    return 0;
}

Compilation message

necklace.cpp: In function 'void prefixFunction(std::__cxx11::string, const string&, int*)':
necklace.cpp:16:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < a.size(); i++) {
                     ~~^~~~~~~~~~
necklace.cpp:25:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < b.size(); i++)
                     ~~^~~~~~~~~~
necklace.cpp: In function 'std::tuple<int, int, int> calc(std::__cxx11::string, std::__cxx11::string, bool)':
necklace.cpp:34:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < b.size() - 1; i++) {
                     ~~^~~~~~~~~~~~~~
necklace.cpp:48:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (j + 1 < a.size())
                 ~~~~~~^~~~~~~~~~
necklace.cpp:54:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 y = i - (j + 1 < a.size() ? p2[j + 1] : 0);
                          ~~~~~~^~~~~~~~~~
necklace.cpp:58:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < b.size() - 1; j++)
                         ~~^~~~~~~~~~~~~~
necklace.cpp:63:26: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
         y = b.size() - 1 - y - ans;
             ~~~~~~~~~~~~~^~~

Subtask #1
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 8 ms 376 KB Output is correct
7 Correct 7 ms 376 KB Output is correct
8 Correct 8 ms 376 KB Output is correct
9 Correct 8 ms 376 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 7 ms 376 KB Output is correct
12 Correct 7 ms 376 KB Output is correct
13 Correct 332 ms 496 KB Output is correct
14 Correct 284 ms 468 KB Output is correct
15 Correct 354 ms 468 KB Output is correct
16 Correct 292 ms 376 KB Output is correct
17 Correct 256 ms 476 KB Output is correct
18 Correct 266 ms 376 KB Output is correct
19 Correct 274 ms 424 KB Output is correct
20 Correct 296 ms 504 KB Output is correct
21 Correct 307 ms 504 KB Output is correct