oj.uz

Submission #138182

# Submission time Handle Problem Language Result Execution time Memory
138182 2019-07-29T14:22:00 Z popovicirobert Necklace (Subtask 1-3) (BOI19_necklace1) C++14
85 / 85
 481 ms 71160 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44


/*const int MOD = (int) 1e9 + 7;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}*/

/*int fact[], invfact[];

inline void prec(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    }
    invfact[n] = lgput(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; i--) {
        invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
    }
}

inline int comb(int n, int k) {
    if(n < k) return 0;
    return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}*/

using namespace std;

const int MAXN = 3005;

char a[MAXN + 1], b[MAXN + 1];
int dpa[MAXN + 1][MAXN + 1], dpb[MAXN + 1][MAXN + 1];
int n, m;

char str[2 * MAXN + 1];
int pi[2 * MAXN + 1];

inline void get(char *a, char *b, int n, int m, int dp[MAXN + 1][MAXN + 1]) {
    int i, j;
    for(i = 1; i <= n; i++) {

        int sz = 0;
        for(j = i; j <= n; j++) {
            str[++sz] = a[j];
        }
        str[++sz] = '0';
        for(j = 1; j <= m; j++) {
            str[++sz] = b[j];
        }

        int k = 0;
        for(j = 2; j <= sz; j++) {
            while(k > 0 && str[k + 1] != str[j]) {
                k = pi[k];
            }
            if(str[k + 1] == str[j]) {
                k++;
            }
            pi[j] = k;
            if(j >= n - i + 3) {
                dp[i][j - (n - i) - 2] = pi[j];
            }
        }
    }
}

struct Data {
    int val;
    int posa, posb;
    bool operator <(const Data &other) const {
        return val < other.val;
    }
};

inline Data solve() {
    get(a, b, n, m, dpa);
    get(b, a, m, n, dpb);

    Data ans = {0, 0, 0};
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int cur = dpa[i][j - 1] + dpb[j][i - 1];
            if(cur > ans.val) {
                ans.val = cur;
                ans.posa = i - dpb[j][i - 1];
                ans.posb = j - dpa[i][j - 1];
            }
        }
    }

    return ans;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    //int ;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> a + 1 >> b + 1;
    n = strlen(a + 1), m = strlen(b + 1);

    Data x = solve();
    reverse(a + 1, a + n + 1);
    Data y = solve();
    y.posa = n - y.posa + 1 - y.val + 1;

    if(x < y) {
        swap(x, y);
    }

    cout << x.val << "\n" << x.posa - 1 << " " << x.posb - 1;

    return 0;
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:133:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin >> a + 1 >> b + 1;
            ~~^~~
necklace.cpp:133:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin >> a + 1 >> b + 1;
                     ~~^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1400 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1400 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct
6 Correct 10 ms 4856 KB Output is correct
7 Correct 9 ms 4856 KB Output is correct
8 Correct 9 ms 4344 KB Output is correct
9 Correct 10 ms 4728 KB Output is correct
10 Correct 4 ms 4600 KB Output is correct
11 Correct 10 ms 4728 KB Output is correct
12 Correct 10 ms 4604 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1400 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct
6 Correct 10 ms 4856 KB Output is correct
7 Correct 9 ms 4856 KB Output is correct
8 Correct 9 ms 4344 KB Output is correct
9 Correct 10 ms 4728 KB Output is correct
10 Correct 4 ms 4600 KB Output is correct
11 Correct 10 ms 4728 KB Output is correct
12 Correct 10 ms 4604 KB Output is correct
13 Correct 481 ms 71036 KB Output is correct
14 Correct 389 ms 71160 KB Output is correct
15 Correct 454 ms 68856 KB Output is correct
16 Correct 409 ms 70552 KB Output is correct
17 Correct 425 ms 69756 KB Output is correct
18 Correct 451 ms 70648 KB Output is correct
19 Correct 417 ms 70776 KB Output is correct
20 Correct 412 ms 69824 KB Output is correct
21 Correct 417 ms 70008 KB Output is correct