oj.uz

Submission #1077349

# Submission time Handle Problem Language Result Execution time Memory
1077349 2024-08-27T05:39:52 Z komasan Lozinke (COCI17_lozinke) C++14
40 / 100
 1000 ms 10844 KB 
#include<bits/stdc++.h>

using namespace std;

#define el "\n"
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define inpout(x) freopen(x".inp", "r", stdin), freopen(x".out", "w", stdout)

const int maxn = 2e4 + 5;
const ll mod = 1e9 + 7;
const ll base = 31;
const ll Mod[4] = {(ll)1e9 + 1677, (ll)1e9 + 2277, (ll)1e9 + 3577, (ll)1e9 + 3777};

int n, i, ans;
string s[maxn];
vector<ll> Hash[4][maxn];
ll pw[4][maxn];

bool check(int u, int v){
    if (s[u].size() < s[v].size())
        return false;

    for (int j = 1; j <= s[u].size() - s[v].size() + 1; j++){
        bool ok = true;

        int l = j, r = j + s[v].size() - 2;

        for (int k = 0; k < 4; k++)
            if (Hash[k][v][s[v].size() - 1] != (Hash[k][u][r] - Hash[k][u][l - 1] * pw[k][r - l + 1] + Mod[k] * Mod[k]) % Mod[k])
                ok = false;

        if (ok)
            return true;
    }
    return false;
}

signed main(){
    ios;
    cin >> n;

    for (int k = 0; k < 4; k++){
        pw[k][0] = 1;
        for (i = 1; i <= 10; i++)
            pw[k][i] = pw[k][i - 1] * base;
    }

    for (i = 1; i <= n; i++){
        cin >> s[i];
        s[i] = " " + s[i];

        for (int k = 0; k < 4; k++)
            Hash[k][i].resize(s[i].size());

        for (int j = 1; j < s[i].size(); j++)
            for (int k = 0; k < 4; k++)
                Hash[k][i][j] = (Hash[k][i][j - 1] * base + s[i][j] - 'a') % Mod[k];
    }

    for (i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++)
            if (i != j && check(i, j))
                ans++;
    }

    cout << ans;
}

Compilation message

lozinke.cpp: In function 'bool check(int, int)':
lozinke.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int j = 1; j <= s[u].size() - s[v].size() + 1; j++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp: In function 'int main()':
lozinke.cpp:59:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int j = 1; j < s[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3428 KB Output is correct
4 Correct 6 ms 3420 KB Output is correct
5 Correct 26 ms 3676 KB Output is correct
6 Correct 48 ms 3672 KB Output is correct
7 Correct 102 ms 3928 KB Output is correct
8 Correct 80 ms 4020 KB Output is correct
9 Execution timed out 1068 ms 5724 KB Time limit exceeded
10 Execution timed out 1055 ms 6492 KB Time limit exceeded
11 Execution timed out 1045 ms 7004 KB Time limit exceeded
12 Execution timed out 1094 ms 8536 KB Time limit exceeded
13 Execution timed out 1078 ms 9820 KB Time limit exceeded
14 Execution timed out 1071 ms 8284 KB Time limit exceeded
15 Execution timed out 1063 ms 9564 KB Time limit exceeded
16 Execution timed out 1024 ms 10844 KB Time limit exceeded
17 Execution timed out 1068 ms 10844 KB Time limit exceeded
18 Execution timed out 1075 ms 9820 KB Time limit exceeded
19 Execution timed out 1041 ms 9048 KB Time limit exceeded
20 Execution timed out 1042 ms 8792 KB Time limit exceeded