Submission #584376

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
584376	2022-06-27T09:29:23 Z	tengiz05	Necklace (Subtask 4) (BOI19_necklace4)	C++17	3 / 15	1191 ms	756 KB

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

3.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	497 ms	444 KB	Output is correct
2	Partially correct	594 ms	444 KB	Output is partially correct
3	Correct	640 ms	612 KB	Output is correct
4	Partially correct	615 ms	608 KB	Output is partially correct
5	Partially correct	448 ms	620 KB	Output is partially correct
6	Partially correct	279 ms	640 KB	Output is partially correct
7	Correct	1191 ms	660 KB	Output is correct
8	Correct	820 ms	756 KB	Output is correct
9	Partially correct	683 ms	612 KB	Output is partially correct