oj.uz

Submission #966595

# Submission time Handle Problem Language Result Execution time Memory
966595 2024-04-20T06:15:27 Z 12345678 Lozinke (COCI17_lozinke) C++17
90 / 100
 150 ms 3636 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e4+5, mod=1e9+7;

#define ll long long

ll n, c[nx][11], 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]*30)%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
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 9 ms 604 KB Output is correct
7 Correct 12 ms 604 KB Output is correct
8 Correct 12 ms 716 KB Output is correct
9 Correct 55 ms 1796 KB Output is correct
10 Correct 81 ms 1880 KB Output is correct
11 Correct 90 ms 2656 KB Output is correct
12 Incorrect 129 ms 2644 KB Output isn't correct
13 Correct 136 ms 3412 KB Output is correct
14 Correct 150 ms 3636 KB Output is correct
15 Incorrect 141 ms 3476 KB Output isn't correct
16 Correct 129 ms 2704 KB Output is correct
17 Correct 31 ms 2652 KB Output is correct
18 Correct 24 ms 2652 KB Output is correct
19 Correct 144 ms 3376 KB Output is correct
20 Correct 97 ms 2736 KB Output is correct