Submission #1078642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078642		khactrung1912	Lozinke (COCI17_lozinke)	C++14	5 / 100	25 ms	1944 KiB

lozinke

#include <bits/stdc++.h>
using namespace std;

const int MAX = 2e4;
const int MOD = 1e9 + 7;
const int base = 37;

int n;
string S[MAX];

namespace subtask1
{
    long long Hash[MAX][17], Pow[17];

    long long getHash(int i, int l, int r)
    {
        return (((Hash[i][r] - Hash[i][l - 1]) * (Pow[r - l + 1])) + MOD) % MOD; 
    }

    bool cmp(string a, string b)
    {
        return a.size() > b.size();
    }

    void solve()
    {
        sort(S + 1, S + n + 1, cmp);
        Pow[0] = 1;
        for (int i = 1; i <= 12; i++) Pow[i] = (Pow[i - 1] * base + MOD) % MOD;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < S[i].size(); j++)
            {
                //Hash[i][j + 1] = (Hash[i][j] * base + int(S[i][j]) - int('a') + 1 + MOD) % MOD;
                Hash[i][j + 1] = (Hash[i][j] * base + int(S[i][j]) - int('a') + 1 + MOD) % MOD;
                cerr << Hash[i][j + 1] << " ";
            }
            cerr << "\n";
            
        }
        cerr << getHash(1, 2, 2) << "\n";
        int res = 0;
        for (int i = 1; i <= n - 1; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                if (S[i].size() == S[j].size() and getHash(i, 1, S[i].size()) == getHash(j, 1, S[j].size())) 
                {
                    res += 2;
                    continue;
                }
                else if (S[i].size() == S[j].size()) continue;
                long long t = getHash(j, 1, S[j].size());
                cerr << t << "\n";
                for (int k = 1; k <= S[i].size() - S[j].size() + 1; k++)
                {
                    if (getHash(i, k, k + S[j].size() - 1) == t) 
                    {
                        res++;
                        break;
                    }
                }
            }
        }
        cout << res;
    }
}

namespace sub1
{
	bool cmp(string a, string b)
    {
        return a.size() > b.size();
    }
	void solve()
	{
		sort(S + 1, S + n + 1, cmp);
		int res = 0;
		for (int i = 1; i <= n - 1; i++)
		for (int j = i + 1; j <= n; j++)
		{
			for (int ii = 0; ii < S[i].size() - S[j].size() + 1; ii++)
			{
				int cnt = 0;
				int jj = ii;
				while (S[i][jj] == S[j][cnt] and cnt < S[j].size()) jj++, cnt++;
				if (cnt == S[j].size())
				{
					if (S[i].size() == S[j].size()) res += 2;
					else res++;
				}
			}
		}
		cout << res;
	}
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    cin >> S[i];
    if (n <= 2000) sub1::solve();
}

Compilation message (stderr)

lozinke.cpp: In function 'void subtask1::solve()':
lozinke.cpp:32:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             for (int j = 0; j < S[i].size(); j++)
      |                             ~~^~~~~~~~~~~~~
lozinke.cpp:55:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |                 for (int k = 1; k <= S[i].size() - S[j].size() + 1; k++)
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp: In function 'void sub1::solve()':
lozinke.cpp:82:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    for (int ii = 0; ii < S[i].size() - S[j].size() + 1; ii++)
      |                     ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:86:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     while (S[i][jj] == S[j][cnt] and cnt < S[j].size()) jj++, cnt++;
      |                                      ~~~~^~~~~~~~~~~~~
lozinke.cpp:87:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     if (cnt == S[j].size())
      |         ~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 100