oj.uz

Submission #1081198

# Submission time Handle Problem Language Result Execution time Memory
1081198 2024-08-29T19:37:31 Z Joshua_Andersson Necklace (Subtask 1-3) (BOI19_necklace1) C++14
25 / 85
 1500 ms 1628 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
const int inf = int(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)

inline void fast() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

pair<int,p2> best(string a, string b, bool rev)
{
    int ret = -1;
    p2 r = p2(-1, -1);
    vvi lcp(sz(a), vi(sz(b)));
    rep(starta, sz(a))
    {
        repp(startb, 1, sz(b))
        {
            int rp = 0;
            rep(rlen, 1000)
            {
                int i = starta - rlen;
                int j = startb;
                if (i<0||j+rlen -1 >= sz(b)) break;
                bool good = 1;
                rep(k, rlen)
                {
                    good &= a[i] == b[j];
                    i++;
                    j++;
                }
                if (good) rp = rlen;
            }
            int lp = 0;
            repp(llen, 1, 1000)
            {
                int i = starta;
                int j = startb - llen;
                if (j < 0 || i + llen - 1 >= sz(a)) break;
                bool good = 1;
                rep(k, llen)
                {
                    good &= a[i] == b[j];
                    i++;
                    j++;
                }
                if (good) lp = llen;
            }

            if (rp+lp>ret)
            {
                //assert(rp + lp != 84);
                r = { starta-rp,startb-lp };
                if (rev) r.second = sz(b) - r.second - rp-lp;
                ret = rp+lp;
            }
        }
    }
    return { ret, r };
}

signed main()
{
    fast();

    string a, b;
    cin >> a >> b;
    pair<int, p2> ans = { -1000,p2(0,0) };
    ans = max(ans, best(a, b, 0));
    reverse(all(b));
    ans = max(ans, best(a, b, 1));
    cout << ans.first << "\n" << ans.second.first << " " << ans.second.second;

    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 348 KB Output is correct
2 Correct 27 ms 348 KB Output is correct
3 Correct 13 ms 348 KB Output is correct
4 Correct 15 ms 348 KB Output is correct
5 Correct 21 ms 532 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 348 KB Output is correct
2 Correct 27 ms 348 KB Output is correct
3 Correct 13 ms 348 KB Output is correct
4 Correct 15 ms 348 KB Output is correct
5 Correct 21 ms 532 KB Output is correct
6 Execution timed out 1559 ms 1628 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 348 KB Output is correct
2 Correct 27 ms 348 KB Output is correct
3 Correct 13 ms 348 KB Output is correct
4 Correct 15 ms 348 KB Output is correct
5 Correct 21 ms 532 KB Output is correct
6 Execution timed out 1559 ms 1628 KB Time limit exceeded
7 Halted 0 ms 0 KB -