oj.uz

답안 #1083468

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1083468 2024-09-03T08:56:33 Z Joshua_Andersson Necklace (Subtask 1-3) (BOI19_necklace1) C++14
85 / 85
 1398 ms 808 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
typedef uint64_t ull;
struct H {
    ull x; H(ull x = 0) : x(x) {}
    H operator+(H o) { return x + o.x + (x + o.x < x); }
    H operator-(H o) { return *this + ~o.x; }
    H operator*(H o) {
        auto m = (__uint128_t)x * o.x;
        return H((ull)m) + (ull)(m >> 64);
    }
    ull get() const { return x + !~x; }
    bool operator==(H o) const { return get() == o.get(); }
    bool operator!=(H o) const { return !(*this == o); }
    bool operator<(H o) const { return get() < o.get(); }
};
static const H C = (ll)1e11 + 3; // (order ~ 3e9; random also ok)

struct HashInterval {
    vector<H> ha, pw;
    HashInterval(string& str) : ha(sz(str) + 1), pw(ha) {
        pw[0] = 1;
        repp(i, 0, sz(str))
            ha[i + 1] = ha[i] * C + str[i],
            pw[i + 1] = pw[i] * C;
    }
    H hashInterval(int a, int b) { // hash [a, b)
        b++;
        return ha[b] - ha[a] * pw[b - a];
    }
};



pair<int, p2> best(string a, string b, bool rev)
{
    int ret = -1;
    p2 r = p2(-1, -1);
    HashInterval h1(a);
    HashInterval h2(b);
    mt19937 rng;
    uniform_int_distribution<int> da(0, sz(a) - 1);
    uniform_int_distribution<int> db(0, sz(b) - 1);
    int l = 10;
    auto start = chrono::high_resolution_clock::now();

    while (chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() < 700)
    {
        int aa = da(rng);
        int ab = aa;
        int ba = db(rng);
        int bb = ba;


        int lo = -1;
        int hi = 4001;
        while (lo + 1 < hi)
        {
            int mid = (lo + hi) / 2;
            if (aa + mid >= sz(a) || ba + mid >= sz(b) || h1.hashInterval(aa, aa + mid) != h2.hashInterval(ba, ba + mid))
            {
                hi = mid;
            }
            else lo = mid;
        }
        aa += hi;
        ba += hi;

        lo = -1;
        hi = 4001;
        while (lo + 1 < hi)
        {
            int mid = (lo + hi) / 2;
            if (ab - 1 - mid < 0 || bb - 1 - mid < 0 || h1.hashInterval(ab - 1 - mid, ab - 1) != h2.hashInterval(bb - 1 - mid, bb - 1))
            {
                hi = mid;
            }
            else lo = mid;
        }
        ab -= hi;
        bb -= hi;


        //startb = sb;
        //startb = sb;
        //assert(starta != 1830);
        int starta = aa;
        int startb = bb;
        if (rand() % 2)
        {
            starta = ab;
            startb = ba;
        }

        int rp = 0;
        repp(rlen, 1, l * 2 + 1)
        {
            int i = starta - rlen;
            int j = startb;
            if (i < 0 || j + rlen - 1 >= sz(b)) break;
            bool good = h1.hashInterval(i, i + rlen - 1) == h2.hashInterval(j, j + rlen - 1);
            if (good) rp = rlen;
        }
        int lp = 0;
        repp(llen, 1, l * 2 + 1)
        {
            int i = starta;
            int j = startb - llen;
            if (j < 0 || i + llen - 1 >= sz(a)) break;
            bool good = h1.hashInterval(i, i + llen - 1) == h2.hashInterval(j, j + llen - 1);
            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;
            //assert(r != p2(18, 54));
            ret = rp + lp;
            l = max(l, ret);
        }
    }


    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

# 결과 실행 시간 메모리 Grader output
1 Correct 1392 ms 440 KB Output is correct
2 Correct 1398 ms 436 KB Output is correct
3 Correct 1394 ms 344 KB Output is correct
4 Correct 1391 ms 436 KB Output is correct
5 Correct 1394 ms 436 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1392 ms 440 KB Output is correct
2 Correct 1398 ms 436 KB Output is correct
3 Correct 1394 ms 344 KB Output is correct
4 Correct 1391 ms 436 KB Output is correct
5 Correct 1394 ms 436 KB Output is correct
6 Correct 1394 ms 448 KB Output is correct
7 Correct 1393 ms 452 KB Output is correct
8 Correct 1396 ms 444 KB Output is correct
9 Correct 1395 ms 344 KB Output is correct
10 Correct 1395 ms 348 KB Output is correct
11 Correct 1394 ms 452 KB Output is correct
12 Correct 1397 ms 448 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1392 ms 440 KB Output is correct
2 Correct 1398 ms 436 KB Output is correct
3 Correct 1394 ms 344 KB Output is correct
4 Correct 1391 ms 436 KB Output is correct
5 Correct 1394 ms 436 KB Output is correct
6 Correct 1394 ms 448 KB Output is correct
7 Correct 1393 ms 452 KB Output is correct
8 Correct 1396 ms 444 KB Output is correct
9 Correct 1395 ms 344 KB Output is correct
10 Correct 1395 ms 348 KB Output is correct
11 Correct 1394 ms 452 KB Output is correct
12 Correct 1397 ms 448 KB Output is correct
13 Correct 1393 ms 348 KB Output is correct
14 Correct 1396 ms 592 KB Output is correct
15 Correct 1389 ms 348 KB Output is correct
16 Correct 1397 ms 552 KB Output is correct
17 Correct 1398 ms 344 KB Output is correct
18 Correct 1393 ms 348 KB Output is correct
19 Correct 1398 ms 540 KB Output is correct
20 Correct 1397 ms 544 KB Output is correct
21 Correct 1394 ms 808 KB Output is correct