oj.uz

Submission #1078720

# Submission time Handle Problem Language Result Execution time Memory
1078720 2024-08-28T05:03:33 Z khactrung1912 Lozinke (COCI17_lozinke) C++14
40 / 100
 1000 ms 10332 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 2904 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 3 ms 2876 KB Output is correct
4 Correct 5 ms 2908 KB Output is correct
5 Correct 29 ms 3164 KB Output is correct
6 Correct 71 ms 3416 KB Output is correct
7 Correct 124 ms 3416 KB Output is correct
8 Correct 78 ms 3588 KB Output is correct
9 Execution timed out 1081 ms 5468 KB Time limit exceeded
10 Execution timed out 1028 ms 5976 KB Time limit exceeded
11 Execution timed out 1082 ms 6492 KB Time limit exceeded
12 Execution timed out 1014 ms 8024 KB Time limit exceeded
13 Execution timed out 1036 ms 9304 KB Time limit exceeded
14 Execution timed out 1056 ms 7772 KB Time limit exceeded
15 Execution timed out 1063 ms 9052 KB Time limit exceeded
16 Execution timed out 1078 ms 10332 KB Time limit exceeded
17 Execution timed out 1051 ms 10328 KB Time limit exceeded
18 Execution timed out 1070 ms 9304 KB Time limit exceeded
19 Execution timed out 1043 ms 8536 KB Time limit exceeded
20 Execution timed out 1061 ms 8540 KB Time limit exceeded