oj.uz

Submission #874226

# Submission time Handle Problem Language Result Execution time Memory
874226 2023-11-16T13:03:28 Z vjudge1 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1356 ms 5468 KB 
#pragma GCC optimize("unroll-loops,O3")

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int PRI = 41;
const int MOD = 1E9 + 7;

int mul(int a, int b) {
    return (1LL * a * b) % MOD;
}

int add(int a, int b) {
    return (a + b) - (a + b >= MOD) * MOD;
}

int stra[405][405], strb[405][405];
int reva[405][405], revb[405][405];

#define ONLINE_JUDGE
void solve() {
    string a, b;
    cin >> a >> b;
    int n = int(a.size()), m = int(b.size());

    for(int l = 0; l < n; l++) {
        int res = 0;
        for(int r = l; r < n; r++) {
            res = mul(res, PRI);
            res = add(res, (a[r] - 'a' +1));
            stra[l][r] = res;
        }
    }

    for(int l = 0; l < m; l++) {
        int res = 0;
        for(int r = l; r < m; r++) {
            res = mul(res, PRI);
            res = add(res, (b[r] - 'a' +1));
            strb[l][r] = res;
        }
    }

    for(int r = n -1; r >= 0; r--) {
        int res = 0;
        for(int l = r; l >= 0; l--) {
            res = mul(res, PRI);
            res = add(res, (a[l] - 'a' +1));
            reva[l][r] = res;
        }
    }

    for(int len = min(n, m); len >= 1; len--) {
        for(int l = 0; l + len -1 < n; l++) {
            for(int r = 0; r + len -1 < m; r++) {
                for(int k = 0; k <= len; k++) {
                    //string x = a.substr(l, len);
                    //reverse(x.begin(), x.end());

                    //cerr << len << " -> " << x.substr(0, k) << " " << b.substr(r + len - k, k) << " :: " << x.substr(k, len - k) << " " << b.substr(r, len - k) << "\n";
                    //cerr << len << " -> " << reva[l + len - k][l + len -1] << " " << strb[r + len - k][r + len -1] << " :: " << reva[l][l + len - k -1] << " " << strb[r][r + len - k -1] << "\n";
                    if(reva[l + len - k][l + len -1] == strb[r + len - k][r + len -1] && reva[l][l + len - k -1] == strb[r][r + len - k -1]) {
                        cout << len << "\n";
                        cout << l << " " << r << "\n";
                        return;
                    }

                    //cerr << len << " -> " << a.substr(l, k) << " " << b.substr(r + len - k, k) << " :: " << a.substr(l + k, len - k) << " " << b.substr(r, len - k) << "\n";
                    //cerr << len << " -> " << stra[l][l + k -1] << " " << strb[r + len - k][r + len -1] << " :: " << stra[l + k][l + len -1] << " " << strb[r][r + len - k -1] << "\n";
                    if(stra[l][l + k -1] == strb[r + len - k][r + len -1] && stra[l + k][l + len -1] == strb[r][r + len - k -1]) {
                        cout << len << "\n";
                        cout << l << " " << r << "\n";
                        return;
                    }
                }
            }
        }
    }

    cout << 0 << "\n";
    cout << 0 << " " << 0 << "\n";
    
    return;
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t = 1; //cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 4 ms 2516 KB Output is correct
4 Correct 4 ms 2504 KB Output is correct
5 Correct 6 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 4 ms 2516 KB Output is correct
4 Correct 4 ms 2504 KB Output is correct
5 Correct 6 ms 2396 KB Output is correct
6 Correct 31 ms 2904 KB Output is correct
7 Correct 53 ms 2652 KB Output is correct
8 Correct 869 ms 2968 KB Output is correct
9 Correct 1124 ms 2792 KB Output is correct
10 Correct 1215 ms 2824 KB Output is correct
11 Correct 1356 ms 2824 KB Output is correct
12 Correct 1319 ms 2816 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 4 ms 2516 KB Output is correct
4 Correct 4 ms 2504 KB Output is correct
5 Correct 6 ms 2396 KB Output is correct
6 Correct 31 ms 2904 KB Output is correct
7 Correct 53 ms 2652 KB Output is correct
8 Correct 869 ms 2968 KB Output is correct
9 Correct 1124 ms 2792 KB Output is correct
10 Correct 1215 ms 2824 KB Output is correct
11 Correct 1356 ms 2824 KB Output is correct
12 Correct 1319 ms 2816 KB Output is correct
13 Runtime error 10 ms 5468 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -