Submission #237062

#	Time	Username	Problem	Language	Result	Execution time	Memory
237062		MrRobot_28	Lozinke (COCI17_lozinke)	C++17	100 / 100	139 ms	1408 KiB

lozinke

#include<bits/stdc++.h>
using namespace std;
const int mod1 = 998244353;
const int mod2 = 1e9 + 7;
signed main() {
	int n;
	cin >> n;
	vector <string> s(n);
	for(int i = 0; i < n; i++)
	{
		cin >> s[i];
	}
	vector <vector <pair <int, int> > > hashes(11);
	for(int i = 0; i < n; i++)
	{
		pair <int, int> hs = make_pair(0, 0);
		for(int j = 0; j < s[i].size(); j++)
		{
			hs.first = (27 * hs.first + s[i][j] - 'a' + 1) % mod1;
			hs.second = (27 * hs.second + s[i][j] - 'a' + 1) % mod2;
		}
		hashes[s[i].size()].push_back(hs);
	}
	for(int i = 0; i < 11;i++)
	{
		sort(hashes[i].begin(), hashes[i].end());
	}
	int ans = 0;
	for(int i = 0; i < n; i++)
	{
		set <pair <int, int> > gethashes;
		for(int j = 0; j < s[i].size(); j++)
		{
			pair <int, int> hs = make_pair(0, 0);
			for(int k = j; k < s[i].size(); k++)
			{
				hs.first = (27 * hs.first + s[i][k] - 'a'+ 1) % mod1;
				hs.second = (27 * hs.second + s[i][k] - 'a' + 1) % mod2;
				if(gethashes.find(hs) != gethashes.end())
				{
					continue;
				} 
				gethashes.insert(hs);
				int it1 = lower_bound(hashes[k - j + 1].begin(), hashes[k - j + 1].end(), hs) - hashes[k - j + 1].begin();
				int it2 = upper_bound(hashes[k - j + 1].begin(), hashes[k - j + 1].end(), hs) - hashes[k - j + 1].begin();
				ans += it2 - it1;
			}
		}
		ans--;
	}
	cout << ans;
    return 0;
}

Compilation message (stderr)

lozinke.cpp: In function 'int main()':
lozinke.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < s[i].size(); j++)
                  ~~^~~~~~~~~~~~~
lozinke.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < s[i].size(); j++)
                  ~~^~~~~~~~~~~~~
lozinke.cpp:35:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k = j; k < s[i].size(); k++)
                   ~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100