Submission #672362

#	Time	Username	Problem	Language	Result	Execution time	Memory
672362		_martynas	Necklace (Subtask 1-3) (BOI19_necklace1)	C++11	25 / 85	394 ms	604 KiB

necklace

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int X = 29;

const int MXN = 3005;

int n, m;
string a, b[2];

ll H_A[MXN], H[2][MXN];
ll XP[MXN];

ll get_a(int l, int r) {
    assert(l <= r);
    return (H_A[r]-(l ? (H_A[l-1]*XP[r-l+1])%MOD : 0)+MOD)%MOD;
}

ll get_b(int k, int l, int r) {
    assert(l <= r);
    return (H[k][r]-(l ? (H[k][l-1]*XP[r-l+1])%MOD : 0)+MOD)%MOD;
}

void init() {
    XP[0] = 1;
    for(int i = 1; i <= max(n, m); i++) {
        XP[i] = (X*XP[i-1])%MOD;
    }
    H_A[0] = a[0]-'a'+1;
    for(int i = 1; i < n; i++) {
        H_A[i] = (X*H_A[i-1]+a[i]-'a'+1)%MOD;
    }
    for(int k = 0; k < 2; k++) {
        H[k][0] = b[k][0]-'a'+1;
        for(int i = 1; i < m; i++) {
            H[k][i] = (X*H[k][i-1]+b[k][i]-'a'+1)%MOD;
        }
    }
    if(a == "zxyabcd" && b[0] == "yxbadctz") {
        // yxbadctz
        // ztcdabxy
        cerr << b[1] << "\n";
        cerr << a << "\n";
        cerr << b[1].substr(4, 2) << " + " << b[1].substr(2, 2) << "\n";
        cerr << (H[1][5]-H[1][3])*XP[2]%MOD << " " << H[1][3]-H[1][1] << "\n";
        cerr << a.substr(3) << "\n";
        cerr << H_A[n-1]-H_A[2] << "\n";
        assert(((H[1][5]-H[1][3]*XP[2]%MOD+MOD)*XP[2]%MOD+(H[1][3]-H[1][1]*XP[2]%MOD+MOD))%MOD
               == (H_A[6]-H_A[2]*XP[4]%MOD+MOD)%MOD);
        assert((get_b(1, 4, 5)*XP[2]%MOD+get_b(1, 2, 3))%MOD == get_a(3, 6));
    }
}

unordered_set<ll> S;
set<string> stringS;
pii check(int len) {
    // check if a[i..i+len]+a[i..i+len] contains b[j..j+len] or reverse b[j..j+len]
    for(int i = 0; i+len <= n; i++) {
        S.clear();
        stringS.clear();
        // a0 a1 a2 a0 a1 a2
        // --------
        //    --------
        //       --------
        for(int j = 0; j < len; j++) {
            ll val = get_a(i+j, i+len-1)*XP[j]%MOD;
            if(j) {
                val += get_a(i, i+j-1);
            }
            //cerr << a.substr(i+j, (i+len-1)-(i+j)+1) << " + " << (j?a.substr(i, j):"") << "\n";
            stringS.insert(a.substr(i+j, (i+len-1)-(i+j)+1)+(j?a.substr(i, j):""));
            S.insert(val%MOD);
        }

//        for(string s : stringS) {
//            cerr << s << "\n";
//        }

        for(int j = 0; j+len <= m; j++) {
            ll val = get_b(0, j, j+len-1);
            auto it = S.find(val);
            if(it != S.end()) {
                return {i, j};
            }
            else {
                assert(stringS.count(b[0].substr(j, len)) == 0);
            }
        }
        for(int j = 0; j+len <= m; j++) {
            ll val = get_b(1, j, j+len-1);
            auto it = S.find(val);
            if(it != S.end()) {
                return {i, m-(j+len-1)-1};
            }
            else {
                if(stringS.count(b[1].substr(j, len))) {
                    cerr << b[1].substr(j, len) << "!\n";
                }
                assert(stringS.count(b[1].substr(j, len)) == 0);
            }
        }
    }
    return {-1, -1};
}

int main() {
    //FASTIO();

    cin >> a >> b[0];
    n = a.size();
    m = b[0].size();
    cerr << "n = " << n << "\n";
    cerr << "m = " << m << "\n";
    b[1] = b[0];
    reverse(all(b[1]));

    init();
    for(int i = min(n, m); i >= 1; i--) {
        pii ans = check(i);
        if(ans.F != -1) {
            cout << i << "\n";
            cout << ans.F << " " << ans.S << "\n";
            break;
        }
    }

    return 0;
}

/*



*/

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