oj.uz

Submission #1078735

# Submission time Handle Problem Language Result Execution time Memory
1078735 2024-08-28T05:26:50 Z khactrung1912 Lozinke (COCI17_lozinke) C++14
40 / 100
 1000 ms 10588 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;
  //  inpout("pass");
    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:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         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 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 2 ms 2908 KB Output is correct
4 Correct 6 ms 2908 KB Output is correct
5 Correct 30 ms 3164 KB Output is correct
6 Correct 49 ms 3420 KB Output is correct
7 Correct 107 ms 3480 KB Output is correct
8 Correct 77 ms 3416 KB Output is correct
9 Execution timed out 1068 ms 5468 KB Time limit exceeded
10 Execution timed out 1073 ms 5980 KB Time limit exceeded
11 Execution timed out 1022 ms 6744 KB Time limit exceeded
12 Execution timed out 1047 ms 8028 KB Time limit exceeded
13 Execution timed out 1004 ms 9560 KB Time limit exceeded
14 Execution timed out 1070 ms 8028 KB Time limit exceeded
15 Execution timed out 1055 ms 9308 KB Time limit exceeded
16 Execution timed out 1077 ms 10588 KB Time limit exceeded
17 Execution timed out 1029 ms 10584 KB Time limit exceeded
18 Execution timed out 1069 ms 9564 KB Time limit exceeded
19 Execution timed out 1014 ms 8536 KB Time limit exceeded
20 Execution timed out 1014 ms 8536 KB Time limit exceeded