oj.uz

Submission #966603

# Submission time Handle Problem Language Result Execution time Memory
966603 2024-04-20T06:22:13 Z 12345678 Lozinke (COCI17_lozinke) C++17
75 / 100
 141 ms 3580 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e4+5, mod=506848159;

#define ll long long

ll n, c[nx][12], sz[nx], res, p[nx], vl[nx];
string s;
map<ll, ll> mp;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    p[0]=1;
    for (int i=1; i<=10; i++) p[i]=(p[i-1]*28)%mod;
    cin>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>s;
        sz[i]=s.size();
        for (int j=1; j<=sz[i]; j++) c[i][j]=s[j-1]-'a'+1;
    }
    for (int i=1; i<=n; i++)
    {
        set<ll> s;
        for (int j=1; j<=sz[i]; j++)
        {
            ll tmp=0;
            for (int k=j; k<=sz[i]; k++)
            {
                tmp=(tmp+c[i][k]*p[k-j])%mod;
                s.insert(tmp);
                if (j==1&&k==sz[i]) vl[i]=tmp;
            }
        }
        for (auto x:s) if (mp.find(x)!=mp.end()) res+=mp[x];
        mp[vl[i]]++;
    }
    mp.clear();
    for (int i=n; i>=1; i--)
    {
        set<ll> s;
        for (int j=1; j<=sz[i]; j++)
        {
            ll tmp=0;
            for (int k=j; k<=sz[i]; k++)
            {
                tmp=(tmp+c[i][k]*p[k-j])%mod;
                s.insert(tmp);
            }
        }
        for (auto x:s) if (mp.find(x)!=mp.end()) res+=mp[x];
        mp[vl[i]]++;
    }
    cout<<res;
}

Subtask #1
75.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 6 ms 2576 KB Output is correct
6 Correct 9 ms 2396 KB Output is correct
7 Correct 11 ms 2396 KB Output is correct
8 Correct 16 ms 2392 KB Output is correct
9 Correct 55 ms 2908 KB Output is correct
10 Incorrect 67 ms 2972 KB Output isn't correct
11 Correct 91 ms 3152 KB Output is correct
12 Incorrect 132 ms 3156 KB Output isn't correct
13 Correct 135 ms 3516 KB Output is correct
14 Incorrect 140 ms 3580 KB Output isn't correct
15 Incorrect 141 ms 3412 KB Output isn't correct
16 Correct 134 ms 2896 KB Output is correct
17 Correct 30 ms 2648 KB Output is correct
18 Correct 29 ms 2688 KB Output is correct
19 Incorrect 138 ms 3412 KB Output isn't correct
20 Correct 93 ms 2880 KB Output is correct