Submission #1083319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083319		Joshua_Andersson	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	53 / 85	1200 ms	856 KiB

necklace

#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 unsigned long long ull;

struct RollingHash
{
    vector<ull> suf, b;
    int mod;
    RollingHash(string& s, ull base = 131, ull mod = 1e9 + 7) : mod(mod), suf(s.size() + 1), b(s.size() + 1)
    {
        b[0] = 1;
        b[1] = base;

        for (int i = sz(s) - 1; i >= 0; i--)
        {
            suf[i] = (suf[i + 1] * base + s[i]) % mod;
        }

        repp(i, 2, s.size() + 1)
        {
            b[i] = b[i - 1] * b[1] % mod;
        }
    }

    ull gethash(int l, int r) // hash s[l, r]
    {
        ull rv = (suf[r + 1] * b[r - l + 1]) % mod;
        return suf[l] + mod * (suf[l] < rv) - rv;
    }
};

struct DoubleHash
{
    RollingHash h1;
    RollingHash h2;
    DoubleHash(string& s, ull mod = 1e9 + 7) : h1(s, 157, mod), h2(s, 131, mod) {}
    ull gethash(int l, int r)
    {
        return (h1.gethash(l, r) << 32) + h2.gethash(l, r);
    }
};

pair<int,p2> best(string a, string b, bool rev)
{
    int ret = -1;
    p2 r = p2(-1, -1);
    DoubleHash h1(a);
    DoubleHash 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();

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

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


        while (ab > 0 && bb > 0 && a[ab-1] == b[bb-1])
        {
            ab--;
            bb--;
        }
        
        int starta = aa;
        int startb = bb;
        if (rand()%2)
        {
            starta = ab;
            startb = ba;
        }
        //if (len+1 < l) continue;
        rounds++;


        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.gethash(i, i + rlen - 1) == h2.gethash(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.gethash(i, i + llen - 1) == h2.gethash(j, j + llen - 1);
            if (good) lp = llen;
        }

        if (rp + lp > ret)
        {
            r = { starta - rp,startb - lp };
            if (rev) r.second = sz(b) - r.second - rp - lp;
            ret = rp + lp;
            l = max(l, ret);
        }
    }
    cerr << "rounds: " << rounds << "\n";

    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;
}

Compilation message (stderr)

necklace.cpp: In constructor 'RollingHash::RollingHash(std::string&, ull, ull)':
necklace.cpp:29:9: warning: 'RollingHash::mod' will be initialized after [-Wreorder]
   29 |     int mod;
      |         ^~~
necklace.cpp:28:17: warning:   'std::vector<long long unsigned int> RollingHash::suf' [-Wreorder]
   28 |     vector<ull> suf, b;
      |                 ^~~
necklace.cpp:30:5: warning:   when initialized here [-Wreorder]
   30 |     RollingHash(string& s, ull base = 131, ull mod = 1e9 + 7) : mod(mod), suf(s.size() + 1), b(s.size() + 1)
      |     ^~~~~~~~~~~
necklace.cpp:13:48: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define repp(i, low, high) for (int i = low; i < high; i++)
......
   40 |         repp(i, 2, s.size() + 1)
      |              ~~~~~~~~~~~~~~~~~~                 
necklace.cpp:40:9: note: in expansion of macro 'repp'
   40 |         repp(i, 2, s.size() + 1)
      |         ^~~~

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 8 / 40