oj.uz

Submission #446597

# Submission time Handle Problem Language Result Execution time Memory
446597 2021-07-22T15:18:55 Z Mamedov Necklace (Subtask 1-3) (BOI19_necklace1) C++17
25 / 85
 1500 ms 108504 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ui unsigned long long
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second
#define oo (1ll << 60)

using namespace std;


const int up = 3003;
const ui base = 421279;
const int mod = 2100003007;

unordered_map<ui, int>SubHash;

ui pw[up];

void preClc() {
    pw[0] = 1;
    for(int i = 1; i < up; ++i) {
        pw[i] = base * pw[i - 1];
    }
}

void CyclicHashs(int pos, ui h, string &s) {
    string tmp = s + s;
    int sz = (int)s.size();
    SubHash[h] = pos;
    for(int i = sz; i < sz + sz - 1; ++i) {
        h = h - pw[sz - 1] * ((ui)(tmp[i - sz] - '`'));
        h = base * h + (ui)(tmp[i] - '`');
        SubHash[h] = pos;
    }
}
void solve() {
    preClc();
    int n, m;
    string a, b;
    cin >> a >> b;

    bool swaped = false;
    if(a.size() > b.size()) {
        swap(a, b);
        swaped = true;
    }

    n = (int)a.size();
    m = (int)b.size();

    /// for all sub-strings store the hash of its lexicographically smallest necklace
    for(int i = 0; i < n; ++i) {
        ui h = 0;
        string s = "";
        for(int j = i; j < n; ++j) {
            h = base * h + (ui)(a[j] - '`');
            s = s + a[j];
            CyclicHashs(i, h, s);
        }
    }

    int res = 0;
    int sa = 0, sb = 0;
    for(int i = 0; i < m; ++i) {
        ui h = 0;
        for(int j = i; j < m; ++j) {
            h = base * h + (ui)(b[j] - '`');
            if(SubHash.count(h)) {
                if(j - i + 1 > res) {
                    res = j - i + 1;
                    sa = SubHash[h];
                    sb = i;
                }
            }
        }
    }
    reverse(b.begin(), b.end());
    for(int i = 0; i < m; ++i) {
        ui h = 0;
        for(int j = i; j < m; ++j) {
            h = base * h + (ui)(b[j] - '`');
            if(SubHash.count(h)) {
                if(j - i + 1 > res) {
                    res = j - i + 1;
                    sa = SubHash[h];
                    sb = m - 1 - j;
                }
            }
        }
    }
    if(swaped) {
        swap(sa, sb);
    }
    cout << res << '\n';
    cout << sa << ' ' << sb << '\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    int t = 1;
    while(t--) {
        solve();
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3508 KB Output is correct
2 Correct 21 ms 3112 KB Output is correct
3 Correct 8 ms 1484 KB Output is correct
4 Correct 14 ms 2808 KB Output is correct
5 Correct 34 ms 6396 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3508 KB Output is correct
2 Correct 21 ms 3112 KB Output is correct
3 Correct 8 ms 1484 KB Output is correct
4 Correct 14 ms 2808 KB Output is correct
5 Correct 34 ms 6396 KB Output is correct
6 Correct 1387 ms 91088 KB Output is correct
7 Execution timed out 1594 ms 108504 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3508 KB Output is correct
2 Correct 21 ms 3112 KB Output is correct
3 Correct 8 ms 1484 KB Output is correct
4 Correct 14 ms 2808 KB Output is correct
5 Correct 34 ms 6396 KB Output is correct
6 Correct 1387 ms 91088 KB Output is correct
7 Execution timed out 1594 ms 108504 KB Time limit exceeded
8 Halted 0 ms 0 KB -