Submission #1130138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130138		qrn	Savez (COCI15_savez)	C++20	120 / 120	73 ms	23944 KiB

savez

#include <bits/stdc++.h>

using namespace std;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define ALL(x) x.begin(), x.end()
#define sz(x) ((int)(x.size()))
#define int long long
#define vi vector<int>
#define pii pair<int, int>

const int MAXN = 1000010;
const int HASH1 = 3137;
const int HASH2 = 10007;
const int MOD = 1000000007;

map<pii, pii> dp;
int powh1[MAXN], powh2[MAXN], previous[MAXN];
int res, res_idx;

void solve() {
    memset(previous, -1, sizeof(previous));
    powh1[0] = powh2[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        powh1[i] = (powh1[i - 1] * HASH1) % MOD;
        powh2[i] = (powh2[i - 1] * HASH2) % MOD;
    }

    int n;
    cin >> n;
    res = 0;
    res_idx = -1;

    for (int j = 0; j < n; ++j) {
        string s;
        cin >> s;
        int m = sz(s);
        int h_front1 = 0, h_back1 = 0;
        int h_front2 = 0, h_back2 = 0;
        int best = 0;

        for (int i = 0; i < m; ++i) {
            h_back1 = (h_back1 * HASH1 + s[m - 1 - i]) % MOD;
            h_front1 = (h_front1 + powh1[i] * s[i]) % MOD;

            h_back2 = (h_back2 * HASH2 + s[m - 1 - i]) % MOD;
            h_front2 = (h_front2 + powh2[i] * s[i]) % MOD;

            if (h_front1 == h_back1 && h_front2 == h_back2) {
                auto it = dp.find({h_front1, h_front2});
                if (it != dp.end() && best < it->second.first) {
                    best = it->second.first;
                    previous[j] = it->second.second;
                }
            }
        }

        dp[{h_front1, h_front2}] = {best + 1, j};

        if (best + 1 > res) {
            res = best + 1;
            res_idx = j;
        }
    }

    cout << res << endl;
}

signed main() {
    SPEED;
    solve();
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12