oj.uz

Submission #1099964

# Submission time Handle Problem Language Result Execution time Memory
1099964 2024-10-12T09:26:26 Z andrei_iorgulescu Necklace (Subtask 1-3) (BOI19_necklace1) C++14
25 / 85
 1500 ms 600 KB 
#include <bits/stdc++.h>

using namespace std;

int n, m;
string aaa, bbb;
char a[3005], b[3005];

struct sol
{
    int lungime = 0, p1 = 0, p2 = 0;
};

int k;
char s[6005], revs[6005];
int kmp[6005], revkmp[6005];///kmp[i] = cel mai lung prefix al lui s care e sufix al lui s[1...i], de lungime strict sub i

void build_kmps()
{
    memset(kmp, 0, sizeof(kmp));
    memset(revkmp, 0, sizeof(revkmp));
    /*kmp[1] = 0;
    for (int i = 2; i <= k; i++)
    {
        kmp[i] = kmp[i - 1] + 1;
        while (kmp[i] != 0 and s[i] != s[kmp[i]])
            kmp[i] = kmp[kmp[i]];
    }
    revkmp[1] = 0;
    for (int i = 2; i <= k; i++)
    {
        revkmp[i] = revkmp[i - 1] + 1;
        while (revkmp[i] != 0 and revs[i] != revs[revkmp[i]])
            revkmp[i] = revkmp[revkmp[i]];
    }*/
    for (int i = 1; i <= k; i++)
    {
        for (int j = 1; j < i; j++)
        {
            bool boo = true;
            for (int q = 1; q <= j; q++)
                if (s[q] != s[i - j + q])
                    boo = false;
            if (boo)
                kmp[i] = j;
        }
    }
    for (int i = 1; i <= k; i++)
    {
        for (int j = 1; j < i; j++)
        {
            bool boo = true;
            for (int q = 1; q <= j; q++)
                if (revs[q] != revs[i - j + q])
                    boo = false;
            if (boo)
                revkmp[i] = j;
        }
    }
}

sol solve()
{
    sol ans;
    ans.lungime = 0;
    for (int p1 = 1; p1 <= n + 1; p1++)
    {
        k = 0;
        for (int i = p1; i <= n; i++)
            s[++k] = a[i];
        s[++k] = '$';
        for (int i = 1; i <= m; i++)
            s[++k] = b[i];
        s[++k] = '%';
        for (int i = 1; i < p1; i++)
            s[++k] = a[i];
        for (int i = 1; i <= k; i++)
            revs[i] = s[k + 1 - i];
        build_kmps();
        for (int p2 = 1; p2 <= m + 1; p2++)
        {
            int l1 = kmp[n - p1 + p2 + 1];
            int l2 = revkmp[m - p2 + p1 + 1];
            sol cur;
            cur.lungime = l1 + l2;
            cur.p1 = p1 - l2;
            cur.p2 = p2 - l1;
            if (cur.lungime > ans.lungime)
                ans = cur;
        }
    }
    return ans;
}

int main()
{
    cin >> aaa >> bbb;
    n = aaa.size();
    m = bbb.size();
    for (int i = 1; i <= n; i++)
        a[i] = aaa[i - 1];
    for (int i = 1; i <= m; i++)
        b[i] = bbb[i - 1];
    sol sol1 = solve();
    reverse(b + 1, b + m + 1);
    sol sol2 = solve();
    sol2.p2 = m + 1 - (sol2.p2 + sol2.lungime - 1);
    if (sol2.lungime > sol1.lungime)
        swap(sol1, sol2);
    cout << sol1.lungime << '\n' << sol1.p1 - 1 << ' ' << sol1.p2 - 1;
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 348 KB Output is correct
2 Correct 311 ms 464 KB Output is correct
3 Correct 173 ms 348 KB Output is correct
4 Correct 240 ms 600 KB Output is correct
5 Correct 288 ms 596 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 348 KB Output is correct
2 Correct 311 ms 464 KB Output is correct
3 Correct 173 ms 348 KB Output is correct
4 Correct 240 ms 600 KB Output is correct
5 Correct 288 ms 596 KB Output is correct
6 Execution timed out 1574 ms 348 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 348 KB Output is correct
2 Correct 311 ms 464 KB Output is correct
3 Correct 173 ms 348 KB Output is correct
4 Correct 240 ms 600 KB Output is correct
5 Correct 288 ms 596 KB Output is correct
6 Execution timed out 1574 ms 348 KB Time limit exceeded
7 Halted 0 ms 0 KB -