제출 #518586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
518586		K4YAN	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	9 / 85	1551 ms	448 KiB

necklace

//Be Name Khoda

#include<bits/stdc++.h>
#pragma GCC optmize("Ofast,unroll-loops")
#pragma GCC target ("avx2,tune=native")

using namespace std;

#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<pll, ll>

const int mxn = 3e3 + 16;
const ll md = 1e9 + 7, md2 = 998244353, p1 = 27, p2 = 31;
ll n, m, q, w, t, sum;
ll g[mxn], g2[mxn], f[mxn], f2[mxn], taq[mxn], qat[mxn];
string s, h;

void input() {

    cin >> s >> h;

}

inline ll tav(ll a, ll b, ll d) {
    ll res = 1;
    while(b > 0) {
        if(b & 1) res *= a; res %= d;
        a *= a; a %= d; b >>= 1;
    }
    return res;
}

inline void GGL() {
    taq[0] = qat[0] = 1;
    taq[1] = tav(p1, md - 2, md); qat[1] = tav(p2, md2 - 2, md2);
    for(int i = 2; i < mxn; i++) {
        taq[i] = taq[i - 1] * taq[1] % md;
        qat[i] = qat[i - 1] * qat[1] % md2;
    } return;
}

inline void build_hash() {
    n = int(s.size());
    q = 0, w = 1;
    for(int i = 0; i < n; i++) {
        q = q + (1LL * w * (s[i] - 'a')); q %= md;
        g[i] = q; w *= p1; w %= md;
    } q = 0, w = 1;
    for(int i = 0; i < n; i++) {
        q = q + (1LL * w * (s[i] - 'a')); q %= md2;
        g2[i] = q; w *= p2; w %= md2;
    }
    return;
}
inline void build_hash2() {
    m = int(h.size());
    q = 0, w = 1;
    for(int i = 0; i < m; i++) {
        q = q + (1LL * w * (h[i] - 'a')); q %= md;
        f[i] = q; w *= p1; w %= md;
    } q = 0, w = 1;
    for(int i = 0; i < m; i++) {
        q = q + (1LL * w * (h[i] - 'a')); q %= md2;
        f2[i] = q; w *= p2; w %= md2;
    }
    return;
}

inline pii hashG(int l, int r) {
    if(l == 0) {
        q = g[r - 1], w = g2[r - 1];
        return make_pair(q, w);
    }
    q = g[r - 1] - g[l - 1]; q %= md; q += md; q %= md;
    q = 1LL * q * taq[l] % md;
    w = g2[r - 1] - g2[l - 1]; w %= md2; w += md2; w %= md2;
    w = 1LL * w * qat[l] % md2;
    return make_pair(q, w);
}
inline pii hashF(int l, int r) {
    if(l == 0) {
        q = f[r - 1], w = f2[r - 1];
        return make_pair(q, w);
    }
    q = f[r - 1] - f[l - 1]; q %= md; q += md; q %= md;
    q = 1LL * q * taq[l] % md;
    w = f2[r - 1] - f2[l - 1]; w %= md2; w += md2; w %= md2;
    w = 1LL * w * qat[l] % md2;
    return make_pair(q, w);
}

inline int bs(int a, int b) {
    int mid, l, r;
    l = 1, r = min(n - a, m - b) + 1;
    while(l < r) {
        if(r - l == 1) break;
        mid = (l + r) >> 1;
        if(hashG(a, a + mid) == hashF(b, b + mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    return l;
}
inline int bs2(int a, int b) {
    int mid, l, r;
    l = 0, r = min(1LL * a, m - b - sum) + 1;
    while(l < r) {
        if(r - l == 1) break;
        mid = (l + r) >> 1;
        if(hashG(a - mid, a) == hashF(b + sum, b + sum + mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    return l;
}

void solve() {

    GGL();
    build_hash(); build_hash2();
    t = min(n, m);
    ll ans = 0, st1 = -1, st2 = -1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(s[i] != h[j]) continue;
            sum = bs(i, j);
            w = bs2(i, j); sum += w;
            if(sum > ans) {
                st1 = i - w; st2 = j; ans = sum;
            }
        }
    }
    reverse(all(h));
    build_hash2();
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(s[i] != h[j]) continue;
            sum = bs(i, j);
            w = bs2(i, j); sum += w;
            if(sum > ans) {
                st1 = i - w; st2 = m - j - sum; ans = sum;
            }
        }
    }
    cout << ans << "\n";
    cout << st1 << " " << st2 << "\n";
    return;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve();

    return 0;

}

컴파일 시 표준 에러 (stderr) 메시지

necklace.cpp:4: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
    4 | #pragma GCC optmize("Ofast,unroll-loops")
      | 
necklace.cpp: In function 'long long int tav(long long int, long long int, long long int)':
necklace.cpp:31:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   31 |         if(b & 1) res *= a; res %= d;
      |         ^~
necklace.cpp:31:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   31 |         if(b & 1) res *= a; res %= d;
      |                             ^~~

• Subtask 1: 5 / 25
• Subtask 2: 4 / 20
• Subtask 3: 0 / 40