oj.uz

Submission #234384

# Submission time Handle Problem Language Result Execution time Memory
234384 2020-05-24T06:42:23 Z kartel Lozinke (COCI17_lozinke) C++14
10 / 100
 219 ms 12896 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +100500
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

string s[N];
int i, n, ans, j, hsh, p[N], l, r;
map <int, int> mp;

ll mult(ll x, ll y) {return (x * y) % M;}
ll sm(ll x, ll y) {return (x + y) % M;}

int main()
{
    srand(time(0));
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

//    in("input.txt");
//    out("output.txt");

    cin >> n;

    p[0] = 1;
    for (i = 1; i <= n; i++) p[i] = mult(p[i - 1], 31);

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

        hsh = 0;

        for (j = 0; j < sz(s[i]); j++)
                hsh = sm(hsh, mult(s[i][j] - 'a' + 1, p[j]));

        mp[hsh]++;
    }

    for (i = 1; i <= n; i++)
    {
        for (l = 0; l < sz(s[i]); l++)
        {
            hsh = 0;
            for (r = l; r < sz(s[i]); r++)
            {
                hsh = sm(hsh, mult(s[i][r] - 'a' + 1, p[r - l]));
                ans += mp[hsh];
            }
        }
    }

    cout << ans - n;
}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3456 KB Output isn't correct
2 Incorrect 6 ms 3456 KB Output isn't correct
3 Incorrect 6 ms 3456 KB Output isn't correct
4 Incorrect 7 ms 3456 KB Output isn't correct
5 Incorrect 8 ms 3712 KB Output isn't correct
6 Incorrect 10 ms 3712 KB Output isn't correct
7 Incorrect 12 ms 4096 KB Output isn't correct
8 Correct 18 ms 4608 KB Output is correct
9 Incorrect 28 ms 4736 KB Output isn't correct
10 Incorrect 79 ms 7672 KB Output isn't correct
11 Incorrect 47 ms 5624 KB Output isn't correct
12 Incorrect 219 ms 12896 KB Output isn't correct
13 Incorrect 63 ms 4600 KB Output isn't correct
14 Incorrect 148 ms 11896 KB Output isn't correct
15 Incorrect 204 ms 12792 KB Output isn't correct
16 Incorrect 48 ms 3712 KB Output isn't correct
17 Correct 20 ms 3584 KB Output is correct
18 Incorrect 18 ms 3584 KB Output isn't correct
19 Incorrect 97 ms 8056 KB Output isn't correct
20 Incorrect 29 ms 3584 KB Output isn't correct