Submission #584361

#	Time	Username	Problem	Language	Result	Execution time	Memory
584361		tengiz05	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	5 / 85	12 ms	340 KiB

necklace

#include <bits/stdc++.h>

using i64 = long long;
using namespace std;

int min_cyc(const string &s) 
{
    int n = s.size();
    int res = 0;
    for (int l = 0; l < n; )
    {
        res = l;
        int r = l, p = l + 1;
        for (; r < n; ++r, ++p) /// If there is such string found, then its length wont exceed |s|
        {
            char c = (p < n) ? s[p] : s[p - n]; /// to avoid modulo
            if (s[r] > c) break;
            if (s[r] < c) r = l - 1;
        }        
        l = max(r, l + p - r); /// just skip those (s2 = sx + sx + ... + sx + sy) cases
    }
    return res;
}


struct Hash {
    static constexpr int P = 1000000007, M = 29;
    int n;
    std::vector<int> a, pw;
    Hash(std::string s) : n(s.size()), a(n + 1), pw(n + 1, 1) {
        for (int i = 1; i <= n; i++)
            pw[i] = 1LL * pw[i - 1] * M % P;
        for (int i = 0; i < n; i++)
            a[i + 1] = (1LL * a[i] * M + (s[i] - 'a' + 1)) % P;
    }
    int get(int l, int r) {
        int res = a[r] - 1LL * pw[r - l] * a[l] % P;
        if (res < 0)
            res += P;
        return res;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    string a, b;
    cin >> a >> b;
    
    int lo = 0, hi = std::min(a.size(), b.size()) + 1;
    
    auto work = [&](string a, int x) {
        int n = a.size();
        
        vector<pair<int, int>> b;
        for (int i = 0; i <= n - x; i++) {
            string s = a.substr(i, x);
            int p = min_cyc(s);
            rotate(s.begin(), s.begin() + p, s.end());
            b.emplace_back(Hash(s).get(0, x), i);
        }
        
        sort(b.begin(), b.end());
        return b;
    };
    
    auto get = [&](int len) -> pair<int, int> {
        auto x = work(a, len);
        auto y = work(b, len);
        
        int i = 0;
        
        for (auto [a, b] : x) {
            while (i + 1 < int(y.size()) && y[i].first < a) i++;
            if (y[i].first == a) {
                return {b, y[i].second};
            }
        }
        
        return {-1, -1};
    };
    
    while (lo + 1 < hi) {
        int m = (lo + hi) / 2;
        if (get(m).first != -1) {
            lo = m;
        } else {
            hi = m;
        }
    }
    
    std::cout << lo << "\n";
    
    auto x = get(lo);
    
    std::cout << x.first << " " << x.second << "\n";
    
    return 0;
}

• Subtask 1: 5 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40