oj.uz

Submission #672362

# Submission time Handle Problem Language Result Execution time Memory
672362 2022-12-15T17:00:21 Z _martynas Necklace (Subtask 1-3) (BOI19_necklace1) C++11
25 / 85
 394 ms 604 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 2 ms 312 KB Output is correct
3 Correct 34 ms 344 KB Output is correct
4 Correct 65 ms 328 KB Output is correct
5 Correct 122 ms 340 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 2 ms 312 KB Output is correct
3 Correct 34 ms 344 KB Output is correct
4 Correct 65 ms 328 KB Output is correct
5 Correct 122 ms 340 KB Output is correct
6 Correct 238 ms 576 KB Output is correct
7 Correct 394 ms 604 KB Output is correct
8 Incorrect 178 ms 468 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 2 ms 312 KB Output is correct
3 Correct 34 ms 344 KB Output is correct
4 Correct 65 ms 328 KB Output is correct
5 Correct 122 ms 340 KB Output is correct
6 Correct 238 ms 576 KB Output is correct
7 Correct 394 ms 604 KB Output is correct
8 Incorrect 178 ms 468 KB Output isn't correct
9 Halted 0 ms 0 KB -