제출 #584375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584375		tengiz05	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	17 / 85	1197 ms	788 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 i64 P = 1E12 + 7, M = 29;
    int n;
    i64 x;
    Hash(std::string s) : n(s.size()) {
        x = 0;
        for (int i = 0; i < n; i++)
            x = (1LL * x * M + (s[i] - 'a' + 1)) % P;
    }
    i64 get(int l, int r) {
        return x;
    }
};

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<i64, 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);
            reverse(s.begin(), s.end());
            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: 4 / 20
• Subtask 3: 8 / 40