oj.uz

Submission #584367

# Submission time Handle Problem Language Result Execution time Memory
584367 2022-06-27T09:12:07 Z tengiz05 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
9 / 85
 1500 ms 764 KB 
#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;
    std::vector<i64> 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;
    }
    i64 get(int l, int r) {
        return a[r];
    }
};

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Partially correct 2 ms 212 KB Output is partially correct
3 Correct 2 ms 212 KB Output is correct
4 Partially correct 3 ms 212 KB Output is partially correct
5 Correct 2 ms 212 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Partially correct 2 ms 212 KB Output is partially correct
3 Correct 2 ms 212 KB Output is correct
4 Partially correct 3 ms 212 KB Output is partially correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 19 ms 332 KB Output is correct
7 Partially correct 25 ms 468 KB Output is partially correct
8 Correct 25 ms 340 KB Output is correct
9 Partially correct 22 ms 376 KB Output is partially correct
10 Partially correct 18 ms 364 KB Output is partially correct
11 Partially correct 14 ms 348 KB Output is partially correct
12 Correct 22 ms 368 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Partially correct 2 ms 212 KB Output is partially correct
3 Correct 2 ms 212 KB Output is correct
4 Partially correct 3 ms 212 KB Output is partially correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 19 ms 332 KB Output is correct
7 Partially correct 25 ms 468 KB Output is partially correct
8 Correct 25 ms 340 KB Output is correct
9 Partially correct 22 ms 376 KB Output is partially correct
10 Partially correct 18 ms 364 KB Output is partially correct
11 Partially correct 14 ms 348 KB Output is partially correct
12 Correct 22 ms 368 KB Output is correct
13 Correct 1360 ms 552 KB Output is correct
14 Partially correct 1207 ms 532 KB Output is partially correct
15 Correct 1141 ms 764 KB Output is correct
16 Partially correct 1146 ms 740 KB Output is partially correct
17 Partially correct 1025 ms 708 KB Output is partially correct
18 Partially correct 526 ms 636 KB Output is partially correct
19 Execution timed out 1573 ms 676 KB Time limit exceeded
20 Halted 0 ms 0 KB -