Submission #1078643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078643		khactrung1912	Lozinke (COCI17_lozinke)	C++14	0 / 100	1082 ms	5976 KiB

lozinke

#include<bits/stdc++.h>
using namespace std;
const long long mod1 = 1000000007;
const long long mod2 = 79462751;
long long n, powa[15], powb[15], res;
pair<long long, long long> caidautien;
pair<long long, long long> luugiu, chimotdemnuathoi;
pair<long long, long long> hasha[20005][15];
string s[20005];
pair<long long, long long> hashh(long long l, long long r, long long k)
{
    caidautien.first = ((hasha[k][r].first - hasha[k][l - 1].first * powa[r - l + 1] + mod1*mod1) % mod1);
    caidautien.second = ((hasha[k][r].second - hasha[k][l - 1].second * powb[r - l + 1] + mod2*mod2) % mod2);
    return caidautien;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie();
    cout.tie();
    cin >> n;
    powa[0] = 1;
    powb[0] = 1;
    for (long long i = 1; i <= 12; i++)
    {
        powa[i] = powa[i - 1]*30 % mod1;
        powb[i] = powb[i - 1]*28 % mod2;
    }
    for (long long i = 1; i <= n; i++)
    {
        cin >> s[i];
        s[i] = "!" + s[i];
        for (long long j = 1; j <= s[i].length() - 1; j++)
        {
            hasha[i][j].first = (hasha[i][j - 1].first*30 + (s[i][j] - 'a' + 1)) % mod1;
            hasha[i][j].second = (hasha[i][j - 1].second*28 + (s[i][j] - 'a' + 1)) % mod2;
        }
    }
    res = 0;
    for (long long i = 1; i <= n; i++)
    {
        luugiu = hashh(1, s[i].length() - 1, i);
        for (long long j = 1; j <= n; j++)
        {
            // cout << "\n" << i << " " << j << "\n";
            if (i == j || s[i].length() > s[j].length())
            {
                continue;
            } 
            if (s[i] == s[j] && i > j)
            {
                continue;
            }
            for (long long k = 1; k <= s[j].length() - s[i].length() + 1; k++)
            {
                // cout << k << " " << k + s[i].length() - 2 << " - ";
                chimotdemnuathoi = hashh(k, k + s[i].length() - 2, j);
                if (chimotdemnuathoi.first == luugiu.first && chimotdemnuathoi.second == luugiu.second)
                {
                    res++;
                    // cout << "ok\n";
                    break;
                }
            }
        }
    }
    cout << res;
}

Compilation message (stderr)

lozinke.cpp: In function 'int main()':
lozinke.cpp:33:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (long long j = 1; j <= s[i].length() - 1; j++)
      |                               ~~^~~~~~~~~~~~~~~~~~~~
lozinke.cpp:54:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for (long long k = 1; k <= s[j].length() - s[i].length() + 1; k++)
      |                                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100