oj.uz

답안 #584375

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
584375 2022-06-27T09:28:16 Z tengiz05 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
17 / 85
 1197 ms 788 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;
    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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Partially correct 1 ms 212 KB Output is partially correct
3 Correct 1 ms 212 KB Output is correct
4 Partially correct 1 ms 212 KB Output is partially correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Partially correct 1 ms 212 KB Output is partially correct
3 Correct 1 ms 212 KB Output is correct
4 Partially correct 1 ms 212 KB Output is partially correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 11 ms 340 KB Output is correct
7 Partially correct 13 ms 344 KB Output is partially correct
8 Correct 13 ms 340 KB Output is correct
9 Partially correct 13 ms 356 KB Output is partially correct
10 Partially correct 13 ms 360 KB Output is partially correct
11 Partially correct 9 ms 364 KB Output is partially correct
12 Correct 13 ms 368 KB Output is correct

Subtask #3
8.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Partially correct 1 ms 212 KB Output is partially correct
3 Correct 1 ms 212 KB Output is correct
4 Partially correct 1 ms 212 KB Output is partially correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 11 ms 340 KB Output is correct
7 Partially correct 13 ms 344 KB Output is partially correct
8 Correct 13 ms 340 KB Output is correct
9 Partially correct 13 ms 356 KB Output is partially correct
10 Partially correct 13 ms 360 KB Output is partially correct
11 Partially correct 9 ms 364 KB Output is partially correct
12 Correct 13 ms 368 KB Output is correct
13 Correct 702 ms 452 KB Output is correct
14 Partially correct 659 ms 512 KB Output is partially correct
15 Correct 627 ms 788 KB Output is correct
16 Partially correct 608 ms 648 KB Output is partially correct
17 Partially correct 574 ms 656 KB Output is partially correct
18 Partially correct 298 ms 604 KB Output is partially correct
19 Correct 1197 ms 536 KB Output is correct
20 Correct 833 ms 700 KB Output is correct
21 Correct 689 ms 640 KB Output is correct